给定一个长度为 $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)$，表示序列的长度和参数 $K$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 100{,}000)$。

第三行包含一个整数 $M$ $(1 \le M \le 100{,}000)$，表示查询的个数。

接下来 $M$ 行，每行包含两个整数 $l, r$ $(1 \le l \le r \le N)$，表示一个查询。

输出格式

对于每个查询，输出一行一个整数表示答案。

样例

样例输入

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

样例输出

3
1
1
1