CF1485B Replace and Keep Sorted

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]$.

Idea

对于 $a_{l},a_{l+1},\cdots,a_r$，我们只考虑更换其中一个位置的值，使得原序列仍然保持严格递增的性质，就能得到 $k-\text{similar}$ 的数组 $b$。

对于 $l<i<r$，$a[i]$ 可更换为 $a_{i-1}+1,\cdots,a_{i}-1,a_{i}+1,\cdots,a_{i+1}-1$，共 $a_{i+1}-a_{i-1}-2$ 种方案；累加得，$\sum\limits_{i=l+1}^{r-1}(a_{i+1}-a_{i-1}-2)=a_r+a_{r-1}-a_{l-1}-a_l-2\times(r-l-1)$。

对于 $a_l$，需要在 $1\sim a_{l+1}-1$ 中挑一个数字，讨论 $a_l$ 是否为 $1$，得到的方案数都为 $a_{l+1}-2$；对于 $a_r$，需要在 $a_{r-1}+1\sim k$ 中挑选一个数字，讨论 $a_r$ 是否为 $k$，得到的方案数都为 $k-a_{r-1}-1$。

综上所述，总方案数为 $a_r-a[l]-2\times(r-l)+k-1$。

Code

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1485B
Date: 2021 Feb. 28th
Description: Math
*******************************************************************/
#include<iostream>
using namespace std;
const int N=100005;
int n,q,k;
int a[N];
int main(){
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		cout<<a[r]-a[l]-2*(r-l)+k-1<<endl;
	}
	return 0;
}