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.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;



public class CodeForcesB {
	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; 
        }
        int[] nextArray(int n)
        {
        	int arr[]=new int[n];
        	for(int i=0;i<n;i++)
        		arr[i]=nextInt();
        	return arr;
        }
    }
	static boolean palin(char[] arr)
	{
		if(arr.length==1)
			return false;
		for(int i=0;i<arr.length/2;i++)
			if(arr[i]!=arr[arr.length-1-i])
				return false;
		return true;
	}
	static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0)
          return b;
        if (b == 0)
          return a;
      
        // base case
        if (a == b)
            return a;
      
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
	static boolean palin(String all)
	{
		for(int i=0;i<all.length()-1;i++)
		{
			for(int j=0;j<=i;j++)
			{
				if(palin(all.substring(j,all.length()-i+j).toCharArray()))
					return true;
			}
		}
		return false;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
			FastReader fs=new FastReader();
			PrintWriter out=new PrintWriter(System.out);
			//out.print("111");
			//int T=fs.nextInt();
			//while(T-->0)
			{
				int n=fs.nextInt(),q=fs.nextInt(),k=fs.nextInt();
				//long x=fs.nextLong();
				//int[] hnv=new int[n];
				//long[] arr=new long[n];
				int arr[]=fs.nextArray(n);
				int[] tem=new int[n];
				if(n>1)
				for(int i=0;i<n;i++)
				{
					if(i==0)
						tem[0]=arr[1]-2;
					else if(i==n-1)
						tem[i]=k-arr[i-1]-1;
					else {
						tem[i]=arr[i+1]-arr[i-1]-2;
					}
					//System.out.println(tem[i]);
					if(i>0)
						tem[i]+=tem[i-1];
					//System.out.println(tem[i]);
				}
				for(int i=1;i<=q;i++)
				{
					int ans=0;
					int l=fs.nextInt(),h=fs.nextInt();
					if(l==h)
					{
						System.out.println(k-1);
						continue;
					}
					//System.out.println(ans);
					if(h-l>=2)
					{
					ans=tem[h-2]-tem[l-1];
					}
					//System.out.println(ans);
					//if(l!=1)
						ans+=arr[l]-2;
					//if(h!=n)
						ans+=k-arr[h-2]-1;
					System.out.println(ans);
				}
				
				
			}
	}

}
