I WANNA！

题目描述

你说得对，但是I WANNA!是一款由JesperErlandsen开发的2D像素风平台跳越设计游戏，在作者精心设计的有趣地图中，你将扮演一位手持手枪的小人，在不断重开的游戏中发现自虐的真相...

Orange学长最近接触到了I WANNA这款"十分好玩"的游戏，在该游戏中，Orange学长将操作一位手持手枪（虽然没啥用）的小人，在各个平台之间进行跳越。地图共有 $N$ 个平台，其中第 $i$ 个平台位于 $P_i$，同时我们保证第 $i$ 个平台一定在第 $i - 1$ 个平台后面，即对于第二个点之后的所有点 $P_i$，满足 $P_i \geq P_{i-1}$。

为了方便你通过这个题，我们可以将平台看成一个点（忽略平台的长度），整张地图看作是一条数轴，小人每次跳越的最远距离为 $K$，你可以跳越到任何一个距离你当前所在的平台不超过 $K$ 的另外一个平台。换句话说，如果你当前处于平台 $P$，那么你可以跳到任何一个平台 $Q$，当且仅当 $Q$ 满足 $|Q - P| \leq K$。而且作者考虑到游戏的可通关性，他保证相邻的两个平台之间的距离一定小于 $K$，即对于任何 $i \geq 2$，满足 $P_i - P_{i - 1} \leq K$。

在Orange学长玩的这个I WANNA版本中，作者为了偷懒，他的每一个关卡都在同一张地图进行，只是每一关的起点和终点的位置位于不同平台上。

现在，我们知道当前共有 $M$ 个关卡，每个关卡的起点和终点位于第 $ST_i$ 和 $ED_i$个平台，请问Orange学长从当前关卡的起点跳跃到终点，最少需要跳越多少次呢？

输入格式

输入共有 $M + 3$ 行，第一行包含两个整数 $N(N\leq 5 \times 10^5)$ 和 $K(K \leq 10^9)$，表示当前地图的平台个数和你的最远跳跃距离。

第二行包含 $N$ 个整数 $P_i$，表示第 $i$ 个平台在数轴上的位置，其满足对于任意$P_i$，$1 \leq P_i \leq 10^{14}$，且当 $i > 1$时，$P_i > P_{i-1}$。

第三行包含一个整数 $M(M \leq 5 \times 10^5)$，表示游戏共有 $M$ 个关卡。

接下来的 $M$ 行，第 $M + i$ 行包含两个整数 $ST_i$ 和 $ED_i$（$1 \leq ST_i < ED_i \leq N$），表示第 $i$ 个关卡的起点和终点所在的平台编号。

输出格式

输出共有 $M$ 行，即对于每个关卡，输出一个整数，代表Orange学长通关所需的最小跳越次数。

样例 #1

样例输入 #1

8 10
1 3 6 13 15 18 19 29
4
1 8
3 7
6 7
5 8

样例输出 #1

4
2
1
2

提示

样例组 #1:

对于第一关:

起点位于第1个平台，终点位于第8个平台。我们第一次可以从第1个平台跳越到第3个平台，跳跃为6-1=5，接着从第三个平台跳到第5个平台，距离为15-6=9，再接着从第5个平台跳跃到第7个平台，距离为19-15=4，最后从第7个平台跳跃到第8个平台，距离为29-19=10，此时到达终点，且每次跳越的距离均不超过10，可以证明这是最优的跳法。