题目描述

有 $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$ 家酒店所需的最小天数。

样例 1

输入

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

输出

4
2
1
2

说明/提示

限制条件

• $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 翻译