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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Replace_Keep_S {  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());
    }
    String nextLine(){
        String str = "";
        try
        {
            str = br.readLine();
        }catch (IOException e){
            e.printStackTrace();
        }
        return str;
    }
    double nextDouble(){
        return Double.parseDouble(next());
    }
}

    public static void main(String[] args) {
       FastReader in = new FastReader();
       int n = in.nextInt();
       int q = in.nextInt();
       long k = in.nextLong();
       long arr[] = new long[n+1];
       for(int i = 1; i <= n; i++){
           arr[i] = in.nextLong();
       }
       long pre[] = new long[n+1];

       for(int i = 1; i <= n; i++){
           if(i == 1){
               pre[i] = 0;
           }else{
               pre[i] = (arr[i] - arr[i-1] - 1);
           }
       }

       for(int i = 1; i <= n; i++){
           pre[i]+=pre[i-1];
       }
       long suff[] = new long[n+1];
       for(int i = n; i >= 1; i--){
           if(i == n){
               suff[i] = 0;
           }else {
               suff[i] = arr[i+1] - arr[i] - 1;
           }
       }
       for(int i = n - 1; i >= 1; i--){
           suff[i] += suff[i+1];
       }
       StringBuilder sb = new StringBuilder();
       while(q-- > 0){
            int l = in.nextInt();
            int r = in.nextInt();

            long ans = pre[r] - pre[l];
            ans += suff[l] - suff[r];
            ans += arr[l] - 1;
            ans += k - arr[r];

            sb.append(ans+"\n");
       }
       System.out.println(sb);
    }
}
