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].
//WHEN IN DOUBT , USE BRUTE FORCE !!!!!!!!!
import java.lang.String;
import java.io.*;
import java.util.*;
import java.util.StringTokenizer;
//class Main    //AtCoder()
//class Solution // Codechef
public class Solution2 //Codeforces
{
    public static void main(String args[])
    {
        try {
            FastReader sc = new FastReader();
            //int TT = sc.nextInt();
            for(int hehe=1 ; hehe  <= 1 ; hehe++){
                int n=sc.nextInt();
                int q=sc.nextInt();
                long k=sc.nextLong();
                long arr[]=new long[n];
                int lb[]=new int[q];
                int ub[]=new int[q];
                for(int i=0;i<n;i++) {
                    //sopln("ENTER "+i);
                    arr[i] = sc.nextLong();
                }
                for(int i=0;i<q;i++){
                    lb[i]=sc.nextInt();
                    ub[i]=sc.nextInt();
                }
                long mem0[]=new long[n];
                for(int i=0;i<n;i++){
                    if(i == 0) {
                        mem0[i] = arr[i] - 1;
                    }
                    else{
                        mem0[i]=arr[i]-arr[i-1]-1;
                    }
                    if(i==n-1){
                        mem0[i]+=Math.max(k-arr[i]-1,0);
                    }
                    else{
                        mem0[i]+=Math.max(arr[i+1]-arr[i]-1,0);
                    }
                    //sopln("STUCK");
                }
                long memo[]=new long[n+1];
                memo[0]=0;
                for(int i=0;i<=n-1;i++){
                    if(i>0) {
                        memo[i] = memo[i - 1] + mem0[i];
                    }
                    else{
                        memo[i]=mem0[i];
                    }
                }
                for(int i=0;i<=q-1;i++){
                    int l=lb[i],r=ub[i];
                    l--;r--;
                    if(l == r){
                        sopln(k-1);
                        continue;
                    }
                    long ans=memo[r-1]-memo[l+1-1];
                    //sop(ans+" ----  ");
                    ans = (ans > 0)?ans : 0;
                    long checkL = ((arr[l+1]-arr[l]) - 1) + (arr[l] - 1);
                    long checkR = ((arr[r]-arr[r-1]) - 1) + (k - arr[r]);
                    sopln(ans +checkL + checkR);
                }
            }
            out.flush();
        }catch (Exception e) {
            sopln(e.toString());
        }
    }
    public final static int d = 256;
    static int MOD = 1000000007;
    static final double PI = Math.PI;
    private static BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
    private static PrintWriter out = new PrintWriter (new OutputStreamWriter (System.out));
    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());
        }

        char nextChar()
        {
            try {
                return (char) (br.read());
            }catch (IOException e){
                return '~';
            }
        }

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

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    static void sop(Object o){System.out.print(o);}
    static double ceil(double d){
        return Math.ceil(d);
    }
    static double floor(double d){
        return Math.floor(d);
    }
    static double round(double d){
        return Math.round(d);
    }
    static void sopln(Object o){System.out.println(o);}
    static void printArray(int[] arr){
        for(int i=0;i<arr.length;i++){
            sop(arr[i]+" ");
        }
        sopln("");
    }
}