← 返回题目列表

Codeforces · 1485/B

B. 替换并保持排序

中文机器翻译题面 查看原题

给定一个正整数 $$$k$$$,如果满足以下条件,则两个数组被称为 $$$k$$$-相似:

- 它们严格增加;
- 它们具有相同的长度;
- 它们的所有元素都是 $$$1$$$ 和 $$$k$$$(含)之间的正整数;
- 它们只有一个位置不同。

给你一个整数 $$$k$$$、一个严格递增的数组 $$$a$$$ 和 $$$q$$$ 查询。对于每个查询,您都会获得两个整数 $$$l_i \leq r_i$$$。您的任务是找出存在多少个数组 $$$b$$$,使得 $$$b$$$ 为 $$$k$$$ - 类似于数组 $$$[a_{l_i},a_{l_i+1}\ldots,a_{r_i}]$$$。

输入

第一行包含三个整数 $$$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 < a_2 < \ldots < a_n$$$。

以下 $$$q$$$ 行中的每一行都包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$)。

输出

打印 $$$q$$$ 行。其中第 $$$i$$$ 应该包含第 $$$i$$$ 查询的答案。

示例

输入 #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

注意

在第一个示例中:

在第一个查询中,有 $$$4$$$ 数组 $$$5$$$ - 类似于 $$$[2,4]$$$:$$$[1,4],[3,4],[2,3],[2,5]$$$。

在第二个查询中,有 $$$3$$$ 数组 $$$5$$$ - 类似于 $$$[4,5]$$$:$$$[1,5],[2,5],[3,5]$$$。