配点 : $800$ 点

問題文

数直線上に $N$ 個の点があり，そのうち $i$ 番目の点は座標 $X_i$ にあります． これらの点は座標の昇順に番号がついています． つまり，すべての $i$ ($1 \leq i \leq N-1$) について，$X_i が成り立ちます. また，整数$K$ が与えられます．

$Q$ 個のクエリを処理してください．

$i$ 番目のクエリでは，整数 $L_i,R_i$ が与えられます． ここで，点の集合 $s$ がよい集合であるとは，以下の条件をすべて満たすことを意味します． よい集合の定義がクエリごとに変わることに注意してください．

• $s$ に含まれる点は，$X_{L_i},X_{L_i+1},\ldots,X_{R_i}$ のいずれかである．
• $s$ に含まれるどの異なる $2$ 点についても，その間の距離が $K$ 以上である．
• $s$ のサイズは，上記の条件を満たす集合の中で最大である．

各クエリごとに，すべてのよい集合の和集合のサイズを求めてください．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $0 \leq X_1
• $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$

出力

各クエリごとに，すべてのよい集合の和集合のサイズを一行に出力せよ．

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

4
2

$1$ つめのクエリでは，最大 $3$ つの点を集合に含めることができます． よい集合は，$\{1,4,7\}$ と $\{1,4,8\}$ の $2$ つです． よって，すべてのよい集合の和集合のサイズは $|\{1,4,7,8\}|=4$ です．

$2$ つめのクエリでは，最大 $1$ つの点を集合に含めることができます． よい集合は，$\{1\}$ と $\{2\}$ の $2$ つです． よって，すべてのよい集合の和集合のサイズは $|\{1,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

4
6
11
2
3