Given a positive integer k, two arrays are called k-similar if:

  * they are strictly increasing; 
  * they have the same length; 
  * all their elements are positive integers between 1 and k (inclusive); 
  * they differ in exactly one position. 



You are given an integer k, a strictly increasing array a and q queries. For each query, you are given two integers l_i ≤ r_i. Your task is to find how many arrays b exist, such that b is k-similar to array [a_{l_i},a_{l_i+1}…,a_{r_i}]. 

Input

The first line contains three integers n, q and k (1≤ n, q ≤ 10^5, n≤ k ≤ 10^9) — the length of array a, the number of queries and number k.

The second line contains n integers a_1, a_2, …,a_n (1 ≤ a_i ≤ k). This array is strictly increasing — a_1 < a_2 < … < a_n.

Each of the following q lines contains two integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ n).

Output

Print q lines. The i-th of them should contain the answer to the i-th query.

Examples

Input


4 2 5
1 2 4 5
2 3
3 4


Output


4
3


Input


6 5 10
2 4 6 7 8 9
1 4
1 2
3 5
1 6
5 5


Output


8
9
7
6
9

Note

In the first example:

In the first query there are 4 arrays that are 5-similar to [2,4]: [1,4],[3,4],[2,3],[2,5].

In the second query there are 3 arrays that are 5-similar to [4,5]: [1,5],[2,5],[3,5].
import java.util.*;
// import java.lang.*;
import java.io.*;

//           THIS TEMPLATE MADE BY AKSH BANSAL.

public class Solution {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        // ________________________________

        // int t = sc.nextInt();
        // StringBuilder output = new StringBuilder();

        // while (t-- > 0) {
        //     int n = sc.n
        //     output.append(solver()).append("\n");
        // }

        // out.println(output);
        // _______________________________

        int n = sc.nextInt();
        int nq = sc.nextInt();
        int k=  sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[][] q = new int[nq][2];
        for(int i=0;i<nq;i++){
            q[i][0] = sc.nextInt();
            q[i][1] = sc.nextInt();
        }
        solver(n,nq,k,arr,q,out);
        // out.println(solver());
        // ________________________________
        out.flush();
    }

    public static void solver(int len, int nq, int k, int[] arr, int[][] q, PrintWriter out) {
        if(k==1){
            for(int i=0;i<nq;i++)
                out.println(0);
        }
        int[] dp = new int[len];
        for(int i=0;i<len;i++){
            if(i==0){
                // dp[i] = arr[i+1]-2;
                dp[i] = 0;// as it will be taken care in the loop below
            }
            else if(i==len-1){
                // dp[i] = k-arr[i-1]-1;
                dp[i] = 0; // same reason as i=0
            }
            else
                dp[i]=arr[i+1]-2-arr[i-1]+dp[i-1];
        }
        for(int i=0;i<nq;i++){
            int start = q[i][0]-1;
            int end = q[i][1]-1;
            if(start==end){
                out.println(k-1);
                continue;
            }
            int res = 0;

            res+=k-arr[end-1]-1;
            res+=arr[start+1]-2;
            res+=dp[end-1]-dp[start];

            out.println(res);
        }
    }
}
