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.*;
import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.LockSupport;

public class Main {

    static class Task {

        public static String roundS(double result, int scale) {
            String fmt = String.format("%%.%df", scale);
            return String.format(fmt, result);
//        DecimalFormat df = new DecimalFormat("0.000000");
//        double result = Double.parseDouble(df.format(result));
        }

        int rt(int x) {
            if (x != fa[x]) {
                int to = rt(fa[x]);
                dp[x] ^= dp[fa[x]];
                fa[x] = to;
                return to;
            }
            return x;
        }

        void combine(int x, int y, int val) {
            int rt1 = rt(x);
            int rt2 = rt(y);

            if (rt1 == rt2) return;

            fa[rt1] = rt2;
            dp[rt1] = dp[x] ^ dp[y] ^ val;
            g--;

        }


        int fa[], dp[];
        int g;


        static int MAXN = 10000;
        static Random rd = new Random(348957438574659L);

        static int[] ch[],val,size,rnd,cnt;
        static int len=0,rt=0;

        // return new node, the node below s
        static int rotate(int s,int d){
            // child
            int x=ch[s][d^1];
            // give me grandson
            ch[s][d^1] = ch[x][d];
            // child become father
            ch[x][d]=s;
            // update size, update new son first
            update(s);
            update(x);
            return x;
        }

        static void update(int s){
            size[s] = size[ch[s][0]] + size[ch[s][1]] + cnt[s];
        }

        // 0 for left, 1 for right
        static int cmp(int x,int num) {
            if (val[x] == num) return -1;
            return num < val[x] ? 0 : 1;
        }

        static int insert(int s,int num) {
            if(s==0){
                s=++len;
                val[s]=num;size[s]=1;rnd[s]=rd.nextInt();cnt[s] = 1;
            }else{
                int d=cmp(s,num);
                if(d!=-1) {
                    ch[s][d]=insert(ch[s][d],num);
                    // father's random should be greater
                    if(rnd[s]<rnd[ch[s][d]]) {
                        s=rotate(s,d^1);
                    }else {
                        update(s);
                    }
                }else{
                    ++cnt[s];++size[s];
                }
            }
            return s;
        }

        static int del(int s,int num) {
            int d = cmp(s, num);
            if (d != -1) {
                ch[s][d] = del(ch[s][d], num);
                update(s);
            }else if (ch[s][0] * ch[s][1] == 0) {
                if(--cnt[s]==0){
                    s = ch[s][0] + ch[s][1];
                }
            } else {
                int k = rnd[ch[s][0]] < rnd[ch[s][1]] ? 0 : 1;
                // k points to smaller random value,then bigger one up
                s = rotate(s, k);
                // now the node with value num become the child
                ch[s][k] = del(ch[s][k], num);
                update(s);
            }
            return s;
        }

        static int getKth(int s, int k){
            int lz = size[ch[s][0]];
            if(k>=lz+1&&k<=lz+cnt[s]){
                return val[s];
            }else if(k<=lz){
                return getKth(ch[s][0], k);
            }else{
                return getKth(ch[s][1], k-lz-cnt[s]);
            }
        }
        // value可能不在树中出现，定义为比自己小的数的个数+1
        static int getRank(int s,int value){
            if(s==0)return 1;
            if(value==val[s])return size[ch[s][0]] + 1;
            if(value<val[s])return getRank(ch[s][0],value);
            return getRank(ch[s][1],value)+size[ch[s][0]] + cnt[s];
        }


        static int getPre(int data){
            int ans= -1;
            int p=rt;
            while(p>0){
                if(data>val[p]){
                    if(ans==-1 || val[p]>val[ans])
                        ans=p;
                    p=ch[p][1];
                }
                else p=ch[p][0];
            }
            return ans!=-1?val[ans]:(-2147483647);
        }

        static int getNext(int data){
            int ans= -1;
            int p=rt;
            while(p>0){
                if(data<val[p]){
                    if(ans==-1 || val[p]<val[ans])
                        ans=p;
                    p=ch[p][0];
                }
                else p=ch[p][1];
            }

            return ans!=-1?val[ans]:2147483647;
        }


        static boolean find(int s,int num){
            while(s!=0){
                int d=cmp(s,num);
                if(d==-1) return true;
                else s=ch[s][d];
            }
            return false;
        }
        static int ans = -10000000;
        static boolean findX(int s,int num){
            while(s!=0){
                if(val[s]<=num){
                    ans = num;
                }
                int d=cmp(s,num);
                if(d==-1) return true;
                else {
                    s = ch[s][d];
                }
            }
            return false;
        }




        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int q = in.nextInt();
            int k = in.nextInt();

            int a[] = in.nextArray(n);

            long s[] = new long[n];

            for(int j=0;j<n;++j){
                long up = j+1<n?a[j+1]:k;
                long down = j-1>=0?a[j-1]:1;

                long num = up-down-2;

                s[j] = num;
                if(j>=1){
                    s[j] += s[j-1];
                }
            }


            for(int j=0;j<q;++j){
                int l = in.nextInt()-1;
                int r = in.nextInt()-1;

                if(l==r){
                    out.println(k-1);continue;
                }
                long num = s[r-1] - s[l];

                 num += a[l+1]-2;
                 num += k-a[r-1]-1;
                 out.println(num);



            }




//            while(true) {
//                int n = in.nextInt();
//
//                int m  =in.nextInt();
//
//                fa = new int[n];
//                dp = new int[n];
//                for(int i=0;i<n;++i){
//                    fa[i] = i;
//                }
//                g =  n;
//                int c = 0;
//                int as[] = new int[n];
//                int bs[] = new int[n];
//                char xs[] = new char[n];
//
//                int at = -1;
//                Set<Integer> st = new HashSet<>();
//
//                for (int i = 0; i < n; ++i) {
//                    String line = in.next();
//                    int p = 0;
//                    int a = 0;
//                    while(Character.isDigit(line.charAt(p))){
//                        a =  a*10 + (line.charAt(p)-'0'); p++;
//                    }
//                    char x = line.charAt(p++);
//
//                    int b = 0;
//                    while(p<line.length()){
//                        b =  b*10 + (line.charAt(p)-'0'); p++;
//                    }
//
//                    as[i] = a;
//                    xs[i] = x;
//                    bs[i] = b;
//
//                    if(x=='='){
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]!=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, 0);
//                        }
//                    }else if(x=='<'){
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]>=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, -1);
//                        }
//                    }else{
//                        int r1 = rt(a); int r2 = rt(b);
//                        if(r1==r2){
//                            if(dp[a]<=dp[b]){
//                                c++;
//                                at = i;
//                            }
//                        }else {
//                            combine(a, b, 1);
//                        }
//                    }
//
//
//                }
//                if(g==1||c>=2){
//                    out.println("Impossible");
//                    continue;
//                }
//
//
//                for(int xuan: st){
//
//
//
//
//                }
//
//
//
//
//
//
//            }






        }


        static long mul(long a, long b, long p)
        {
            long res=0,base=a;
            while(b>0)
            {
                if((b&1L)>0)
                    res=(res+base)%p;
                base=(base+base)%p;
                b>>=1;
            }
            return res;
        }

        static long mod_pow(long k,long n,long p){
            long res = 1L;
            long temp = k%p;
            while(n!=0L){
                if((n&1L)==1L){
                    res = mul(res,temp,p);
                }
                temp = mul(temp,temp,p);
                n = n>>1L;
            }
            return res%p;
        }


        public static double roundD(double result, int scale){
            BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
            return bg.doubleValue();
        }



    }
    private static void solve() {
        InputStream inputStream = System.in;
        //InputStream inputStream  = new FileInputStream(new File("D:\\chrome_download\\travel1.in"));
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task task = new Task();
        task.solve(1, in, out);
        out.close();
    }
    public static void main(String[] args) {
       // new Thread(null, () -> solve(), "1", (1 << 10 ) ).start();
        solve();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String nextLine() {
            String line = null;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public char nextChar() {
            return next().charAt(0);
        }
        public int[] nextArray(int n) {
            int res[] = new int[n];
            for (int i = 0; i < n; ++i) {
                res[i] = nextInt();
            }
            return res;
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}