#P1485B. Replace and Keep Sorted

Replace and Keep Sorted

Description

Given a positive integer kk, two arrays are called kk-similar if:

  • they are strictly increasing;
  • they have the same length;
  • all their elements are positive integers between 11 and kk (inclusive);
  • they differ in exactly one position.

You are given an integer kk, a strictly increasing array aa and qq queries. For each query, you are given two integers liril_i \leq r_i. Your task is to find how many arrays bb exist, such that bb is kk-similar to array [ali,ali+1,ari][a_{l_i},a_{l_i+1}\ldots,a_{r_i}].

The first line contains three integers nn, qq and kk (1n,q1051\leq n, q \leq 10^5, nk109n\leq k \leq 10^9) — the length of array aa, the number of queries and number kk.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots,a_n (1aik1 \leq a_i \leq k). This array is strictly increasing  — a1<a2<<ana_1 < a_2 < \ldots < a_n.

Each of the following qq lines contains two integers lil_i, rir_i (1lirin1 \leq l_i \leq r_i \leq n).

Print qq lines. The ii-th of them should contain the answer to the ii-th query.

Input

The first line contains three integers nn, qq and kk (1n,q1051\leq n, q \leq 10^5, nk109n\leq k \leq 10^9) — the length of array aa, the number of queries and number kk.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots,a_n (1aik1 \leq a_i \leq k). This array is strictly increasing  — a1<a2<<ana_1 < a_2 < \ldots < a_n.

Each of the following qq lines contains two integers lil_i, rir_i (1lirin1 \leq l_i \leq r_i \leq n).

Output

Print qq lines. The ii-th of them should contain the answer to the ii-th query.

Samples

样例输入 1

4 2 5
1 2 4 5
2 3
3 4

样例输出 1

4
3

样例输入 2

6 5 10
2 4 6 7 8 9
1 4
1 2
3 5
1 6
5 5

样例输出 2

8
9
7
6
9

Note

In the first example:

In the first query there are 44 arrays that are 55-similar to [2,4][2,4]: [1,4],[3,4],[2,3],[2,5][1,4],[3,4],[2,3],[2,5].

In the second query there are 33 arrays that are 55-similar to [4,5][4,5]: [1,5],[2,5],[3,5][1,5],[2,5],[3,5].