AT_arc060_c [ARC060E] 高橋君とホテル

有 $N$ 家酒店沿一条直线排列。第 $i$ 家酒店位于坐标 $x_i$ 上，其中 $1 \leq i \leq N$。 作为旅行者的高桥君有以下两条信念： - 高桥君一天内的移动距离不会超过 $L$。 - 高桥君不会露宿野外。也就是说，每天结束时他一定要在某家酒店里。 现在有 $Q$ 个询问。对于第 $j$ 个询问（$1 \leq j \leq Q$），给出两个不同的整数 $a_j,\,b_j$。请你对于每个询问，在遵守上述信念的前提下，求出高桥君从第 $a_j$ 家酒店移动到第 $b_j$ 家酒店所需的最小天数。可以保证高桥君一定能从第 $a_j$ 家酒店移动到第 $b_j$ 家酒店。

输入以如下格式从标准输入给出。 > $N$ $x_1$ $x_2$ $\ldots$ $x_N$ $L$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ $\ldots$ $a_Q$ $b_Q$

输出共 $Q$ 行。第 $j$ 行（$1 \leq j \leq Q$）输出高桥君从第 $a_j$ 家酒店移动到第 $b_j$ 家酒店所需的最小天数。

## 限制条件 - $2 \leq N \leq 10^5$ - $1 \leq L \leq 10^9$ - $1 \leq Q \leq 10^5$ - $1 \leq x_1 < x_2 < \ldots < x_N \leq 10^9$ - $x_{i+1} - x_i \leq L$ - $1 \leq a_j, b_j \leq N$ - $a_j \neq b_j$ - $N,\,L,\,Q,\,x_i,\,a_j,\,b_j$ 均为整数 ## 部分得分 - 若数据满足 $N \leq 10^3$ 且 $Q \leq 10^3$，则可获得 $200$ 分。 ## 样例说明 1 对于第 $1$ 个询问，可以按如下方式在 $4$ 天内从第 $1$ 家酒店移动到第 $8$ 家酒店： - 第 $1$ 天，从第 $1$ 家酒店移动到第 $2$ 家酒店。这一天的移动距离为 $2$。 - 第 $2$ 天，从第 $2$ 家酒店移动到第 $4$ 家酒店。这一天的移动距离为 $10$。 - 第 $3$ 天，从第 $4$ 家酒店移动到第 $7$ 家酒店。这一天的移动距离为 $6$。 - 第 $4$ 天，从第 $7$ 家酒店移动到第 $8$ 家酒店。这一天的移动距离为 $10$。 由 ChatGPT 4.1 翻译