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 \leq 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}\ldots,a_{r_i}]$ .

The first line contains three integers $n$ , $q$ and $k$ ( $1\leq n, q \leq 10^5$ , $n\leq k \leq 10^9$ ) — the length of array $a$ , the number of queries and number $k$ .

The second line contains $n$ integers $a_1, a_2, \ldots,a_n$ ( $1 \leq a_i \leq k$ ). This array is strictly increasing — $a_1 < a_2 < \ldots < a_n$ .

Each of the following $q$ lines contains two integers $l_i$ , $r_i$ ( $1 \leq l_i \leq r_i \leq n$ ).

Print $q$ lines. The $i$ -th of them should contain the answer to the $i$ -th query.

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