AT_acl1_d Keep Distances

数轴上有 $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 \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$。 由 ChatGPT 4.1 翻译