题目描述

有 $N$ 家酒店位于一条直线上，第 $i$ 家酒店 $(1 \leq i \leq N)$ 的坐标为 $x_i$。

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

• 他每天最多行驶 $L$ 的距离。
• 他不会露宿野外。也就是说，他必须在一天结束时停留在一家酒店。

给定 $Q$ 个查询。第 $j$ 个查询 $(1 \leq j \leq Q)$ 由两个不同的整数 $a_j$ 和 $b_j$ 描述。对于每个查询，找出 Tak 从第 $a_j$ 家酒店到第 $b_j$ 家酒店所需的最小天数，遵循他的原则。保证无论输入如何，他总能够从第 $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_i < 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$ 分。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $x_1$ $x_2$ $...$ $x_N$ $L$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ ： $a_Q$ $b_Q$

输出

输出 $Q$ 行。第 $j$ 行 $(1 \leq j \leq Q)$ 应包含 Tak 从第 $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

示例输出1

4
2
1
2

对于第 $1$ 个查询，他可以在 $4$ 天内从第 $1$ 家酒店前往第 $8$ 家酒店，过程如下：

• 第 $1$ 天：从第 $1$ 家酒店前往第 $2$ 家酒店，行驶距离为 $2$。
• 第 $2$ 天：从第 $2$ 家酒店前往第 $4$ 家酒店，行驶距离为 $10$。
• 第 $3$ 天：从第 $4$ 家酒店前往第 $7$ 家酒店，行驶距离为 $6$。
• 第 $4$ 天：从第 $7$ 家酒店前往第 $8$ 家酒店，行驶距离为 $10$。