题目描述

在数轴上有 $N$ 个点，第 $i$ 个点位于坐标 $X_i$ 上。这些点按照坐标递增的顺序编号。换言之，对于所有 $i$（$1 \\leq i \\leq N-1$），满足 $X_i < X_{i+1}$。此外，给定一个整数 $K$。

进行 $Q$ 次查询。

在第 $i$ 次查询中，给定两个整数 $L_i$ 和 $R_i$。这里，如果一个点集 $s$ 满足以下条件，则称其为一个好的点集。注意，好的点集的定义在每次查询中可能会有所不同。

• $s$ 中的每个点是 $X_{L_i},X_{L_i+1},\\ldots,X_{R_i}$ 中的一个。
• 对于 $s$ 中的任意两个不同的点，它们之间的距离大于等于 $K$。
• $s$ 的大小是满足上述条件的所有点集中最大的。

对于每个查询，找到所有好的点集的并集的大小。

约束条件

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq K \\leq 10^9$
• $0 \\leq X_1 < X_2 < \\cdots < X_N \\leq 10^9$
• $1 \\leq Q \\leq 2 \\times 10^5$
• $1 \\leq L_i \\leq R_i \\leq N$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $K$ $X_1$ $X_2$ $\\cdots$ $X_N$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ $\\vdots$ $L_Q$ $R_Q$

输出

对于每个查询，在一行中打印所有好的点集的并集的大小。

样例输入 1

5 3
1 2 4 7 8
2
1 5
1 2

样例输出 1

4
2

在第一个查询中，你可以在一个好的点集中最多有 $3$ 个点。存在两个好的点集：$\\{1,4,7\\}$ 和 $\\{1,4,8\\}$。因此，所有好的点集的并集的大小是 $|\\{1,4,7,8\\}|=4$。

在第二个查询中，你可以在一个好的点集中最多有 $1$ 个点。存在两个好的点集：$\\{1\\}$ 和 $\\{2\\}$。因此，所有好的点集的并集的大小是 $|\\{1,2\\}|=2$。

样例输入 2

15 220492538
4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194
5
6 14
1 8
1 13
7 12
4 12

样例输出 2

4
6
11
2
3