题目描述

在一条水平数轴上有 $N$ 间酒店沿直线排列着。其中第 $i$ 间酒店的坐标为 $x_i$。

旅行者老汪有以下两个个人原则：

• 他从不在一天内行驶超过 $L$ 的距离。
• 他从不在野外露宿。也就是说，他必须在一天结束时住在某一间酒店里。

给定 $Q$ 个查询。

第 $j$ 个 $(1 \leq j \leq Q)$ 查询由两个不同的整数 $a_j$ 和 $b_j$ 描述。

对于每个查询，找到旅行者老汪在遵循他的原则的情况下从第 $a_j$ 间酒店到第 $b_j$ 间酒店需要行驶的最少天数。

数据保证旅行者老汪肯定能够从第 $a_j$ 间酒店到达第 $b_j$ 间酒店。

输入格式

第一行，一个整数 $N$。

第二行，$N$ 个整数 $x_1, x_2, \ldots, x_N$，两两之间以一个空格分隔。

第三行，一个整数 $L$。

第四行，一个整数 $Q$。

接下来 $Q$ 行，每行包含两个整数 $a_j$ 和 $b_j$，以一个空格分隔。

输出格式

对于每次询问的 $a_j$ 和 $b_j$，输出一行，包含一个整数，表示旅行者老汪从第 $a_j$ 间酒店到第 $b_j$ 间酒店需要行驶的最少天数。

样例

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

4
2
1
2

说明/提示

样例解释

对于第 $1$ 个查询，他可以在 $4$ 天内从第 $1$ 间酒店到第 $8$ 间酒店旅行，如下所示：

• 第 $1$ 天：从第 $1$ 间酒店到第 $2$ 间酒店行驶。行驶的距离为 $2$。
• 第 $2$ 天：从第 $2$ 间酒店到第 $4$ 间酒店行驶。行驶的距离为 $10$。
• 第 $3$ 天：从第 $4$ 间酒店到第 $7$ 间酒店行驶。行驶的距离为 $6$。
• 第 $4$ 天：从第 $7$ 间酒店到第 $8$ 间酒店行驶。行驶的距离为 $10$。

数据规模与约定

对于 $30\%$ 的数据，$N,Q \le 1000$

对于 $100\%$ 的数据：

• $2 \leq N \leq 10^5$
• $1 \leq L \leq 10^9$
• $1 \leq Q \leq 10^5$
• $1 \leq x_i \lt x_2 \lt \ldots \lt 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$ 都是整数。