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].
#include <bits/stdc++.h>
using namespace std;

#define vec vector
#define ll long long
#define ld long double
#define str string
#define ull unsigned ll
#define ui unsigned int
#define ari(a,n) int a[n]
#define arl(a,n) ll a[n]
typedef vec<int> veci;
typedef vec<char> vecc;
typedef vec<string> vecs;
typedef vec<ll> vecll;
typedef vec<ull> vecull;
typedef vec<double> vecd;
typedef vec<ld> vecld;
typedef pair<int,int> parii;
typedef pair<int,char> paric;
typedef pair<char,char> parcc;
typedef pair<int,str> paris;
typedef pair<ll,ll> parll;
typedef pair<double,double> pardd;
typedef pair<ull,ull> parull;
typedef pair<ld,ld> parld;
typedef pair<char,str> parcs;
#define tin(n) int n; cin>>n
#define tch(c) char n; cin>>c
#define tstr(s) str s; cin>>s
#define tll(n) ll n; cin>>n
#define tull(n) ull n; cin>>n
#define td(n) double n; cin>>n
#define tld(n) ld n; cin>>n
#define in cin>>
#define out cout<<
#define loop(a,b,c,d) for(int(a)=(b);(a)<(c);(a)+=(d))
#define loopd(a,b,c,d) for(int(a)=(b);(a)>(c);(a)-=(d))
#define loopn(a,b,c,d) for(int(a)=(b);(a)<=(c);(a)+=(d))
#define loopsq(a,b,c,d) for(int(a)=(b);(a)*(a)<=(c);(a)+=(d))
#define rep(i,n) loop(i,0,n,1)
#define repn(i,n) loopn(i,1,n,1)
#define repsq(i,s,n) loopsq(i,s,n,1)
#define repd(i,n) loopd(i,n,0,1)
#define repall(a,b) for(auto&(a) : (b))
#define all(a) a.begin(),a.end()
#define sqr(a) (ll)(a*a)
#define setall(a,b) memset(a,b,sizeof(a))
#define f first 
#define s second
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a)) 
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a)) 
#define FORD(a, b, c) for (int(a) = (b); (a) >= (c); --(a)) 
#define FORSQ(a, b, c) for (int(a) = (b); (a) * (a) <= (c); ++(a)) 
#define FORC(a, b, c) for (char(a) = (b); (a) <= (c); ++(a)) 
#define REP(i, n) FOR(i, 0, n) 
#define REPN(i, n) FORN(i, 1, n) 
#define MAX(a, b) a = max(a, b) 
#define MIN(a, b) a = min(a, b) 
#define mp make_pair 
#define pb push_back 
#define allar(arr, sz) arr, arr + sz 
#define sz(v) (int)v.size() 
#define srt(v) sort(all(v)) 
#define revs(v) reverse(all(v)) 
#define srtarr(arr, sz) sort(allar(arr, sz)) 
#define revsarr(arr, sz) reverse(allar(arr, sz)) 
#define prmut next_permutation 
#define till(t) while (t--) 
#define ap(s1,s2) s1=s1.append(s2)

//int MAX=0;
//ll MAXll;
//ull MAXull;
//int N=2e+5;

struct stct
{
   
};

veci ans;
//vecs ans;

void sieve_of_prime(int n,vector<int>* prime)
{
    bool mark[n+1];
    memset(mark,true,sizeof(mark));
    mark[0]=mark[1]=false;
    for(int i=2;i*i<=n;i++)   if(mark[i])   for(int j=2*i;j<=n;j+=i)  mark[j]=false;
    for(int i=2;i<=n;i++) if(mark[i]) prime->push_back(i);
}

void solve()
{
    tin(n);
    tin(q);
    tll(k);

    veci a(n),pr(n),ps(n);  int l,r;
    rep(i,n)
    {
        cin>>a[i];
    }
    rep(i,n)
    {
        if(i==0)
        {
            pr[i]=a[i+1]-2;
            ps[i]=pr[i];
        }
        else if(i==n-1)
        {
            pr[i]=k-a[i-1]-1;
            ps[i]=pr[i]+ps[i-1];
        }
        else
        {
            pr[i]=a[i+1]-a[i-1]-2;
            ps[i]=pr[i]+ps[i-1];
        }
        
    }
    //rep(i,n) cout<<pr[i]<<" "<<ps[i]<<"   ";
    //cout<<endl;
    rep(i,q)
    {
        cin>>l>>r;
        int Ans=0;
        if(l==r){ Ans+=k-1; } //cout<<Ans<<" "; }
        // else if(r==n-1)
        // {
        //     if(r-l>1) Ans+=ps[r-1]-ps[l-1]; cout<<Ans<<" ";
        //     Ans+= k-a[r-2]-1; cout<<Ans<<" ";
        //     Ans+= a[l]-2; cout<<Ans<<" ";
        // }
        else
        {
        if(r-l>1) Ans+=ps[r-2]-ps[l-1]; //cout<<Ans<<" ";
        Ans+= k-a[r-2]-1; //cout<<Ans<<" ";
        Ans+= a[l]-2; //cout<<Ans<<" ";
        } 
        //cout<<endl;
        ans.pb(Ans);
    }
    rep(i,q)
     cout<<ans[i]<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //clock_t t; 
    //t = clock();

    // tin(t);
    // till(t)
    // {
    solve();
    //}
   
    //t = clock() - t; 
    //double time_taken = ((double)t)/CLOCKS_PER_SEC;
    //cout<<"\n"<<time_taken;
    return 0;
}