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].
// Problem: B. Replace and Keep Sorted
// Contest: Codeforces - Codeforces Round #701 (Div. 2)
// URL: https://codeforces.com/contest/1485/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms

//code by: Ravi Khatri @Ravi_Orz
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define F first
#define S second
#define pb push_back
#define f(i,s,n) for(int i=(int)s;i<=(int)n;++i)
#define fr(i,n,s) for(int i=(int)n;i>=s;--i)
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define Fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
#define mod 1000000007
ll n,m,l,r,x;
ll a[1000006];
ll b[1000006];
vi g[1000006];

void solve()
{
	int n,q,k;
	cin>>n>>q>>k;
	vll a(n);
	f(i,0,n-1)cin>>a[i];
	vll  b(n);
	f(i,0,n-2){
		if(i==0){
			b[i]=a[i]-1 + a[i+1]-1-a[i];	
		}
		else{
			b[i]=a[i]-(a[i-1]+1) + a[i+1]-1-a[i];
		}
	}
	b[n-1]=k-a[n-1]+a[n-1]-(a[n-2]+1);
	vll prefb(n);
	prefb[0]=b[0];
	//cout<<prefb[0]<<" ";
	for(int i=1;i<n;i++){
		prefb[i]=prefb[i-1]+b[i];
		//cout<<prefb[i]-prefb[i-1]<<" ";
	}
//	cout<<'\n';
	while(q--){
		int l,r;cin>>l>>r;
		--l,--r;
		ll ans=0;
		if(r-l==1){
			ans=k-a[r]+a[r]-(a[l]+1)+a[l]-1+a[r]-1-a[l];
		}
		else if(l==r){
			cout<<k-1<<'\n';
			continue;
		}
		else 	
		ans=a[l]-1+a[l+1]-1-a[l] +k-a[r]+a[r]-1-a[r-1]+(prefb[r-1]-prefb[l]);
		cout<<ans<<'\n';
	}
}
int main()
{	Fast;
	// int t;cin>>t;
	// while(t--)
	solve();
}