题目描述

数轴上有 $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$ 的大小在满足上述条件的集合中最大。

对于每个查询，求所有好集合的并集的大小。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

对于每个查询，输出所有好集合的并集的大小，每行一个结果。

输入输出样例 #1

输入 #1

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

输出 #1

4
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

说明/提示

限制条件

• $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$
• 输入均为整数。

样例解释 1

对于第 $1$ 个查询，最多可以选择 $3$ 个点组成集合。好集合有 $\{1,4,7\}$ 和 $\{1,4,8\}$ 这两种。因此，所有好集合的并集大小为 $|\{1,4,7,8\}|=4$。对于第 $2$ 个查询，最多只能选择 $1$ 个点组成集合。好集合有 $\{1\}$ 和 $\{2\}$ 这两种。因此，所有好集合的并集大小为 $|\{1,2\}|=2$。