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

给定一个正整数 $k$，若两个数组满足以下条件，则称它们是 $k$-相似的：

• 它们均为严格递增数组；
• 它们的长度相同；
• 所有元素均为介于 $1$ 到 $k$（含端点）之间的正整数；
• 它们在恰好一个位置上的元素不同。

现给出一个整数 $k$、一个严格递增数组 $a$ 以及 $q$ 个查询。对每个查询，给定两个整数 $l_i \leq r_i$。你的任务是：求出满足条件的数组 $b$ 的个数，使得 $b$ 与子数组 $[a_{l_i},a_{l_i+1},\ldots,a_{r_i}]$ 是 $k$-相似的。

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 \lt a_2 \lt \ldots \lt a_n$.

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

第一行包含三个整数 $n$、$q$ 和 $k$（$1\leq n, q \leq 10^5$，$n\leq k \leq 10^9$）—— 分别表示数组 $a$ 的长度、查询次数以及数字 $k$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots,a_n$（$1 \leq a_i \leq k$）。该数组严格递增——即满足 $a_1 \lt a_2 \lt \ldots \lt a_n$。

接下来的 $q$ 行中，每行包含两个整数 $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.

输出 $q$ 行。其中第 $i$ 行应包含第 $i$ 个查询的答案。

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

在第一个示例中：

第一个查询中，有 $4$ 个数组与 $[2,4]$ 是 $5$-相似的：$[1,4],[3,4],[2,3],[2,5]$。

第二个查询中，有 $3$ 个数组与 $[4,5]$ 是 $5$-相似的：$[1,5],[2,5],[3,5]$。