与えられた長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ と整数 $K$ に対して，次のクエリを実行するプログラムを作成せよ:

• l r: $l \le i < j \le r$ かつ $\mathrm{abs}(A_i - A_j) \le K$ を満たす組 $(i, j)$ の個数を出力する．

入力

最初の行には，数列の長さを表す整数 $N$ $(1 \le N \le 100{,}000)$ とパラメータ $K$ $(1 \le K \le 100{,}000)$ の 2 つの整数が含まれる．

二行目には $N$ 個の整数 $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 100{,}000)$ が含まれる．

三行目にはクエリの個数を表す整数 $M$ $(1 \le M \le 100{,}000)$ が含まれる．

次の $M$ 行にはそれぞれ 2 つの整数 $l, r$ $(1 \le l \le r \le N)$ が含まれ，1 つのクエリを表す．

出力

各クエリに対して，答えを表す 1 つの整数を 1 行に出力せよ．

入出力例

入力 1

4 31
1 16 32 64
4
1 4
1 2
2 4
2 3

出力 1

3
1
1
1