给定一个正整数 $$$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]$$$。