E1-gogogo出发咯（go）

题目背景

Lsxszc又没有灵感了$\dots$

Lsxszc：kkkw，你最近有空吗[探头]？

kkkw：我现在在xxx市。

Lsxszc：啊，我也过去吧，正好想找你再出一题。

kkkw：已经出好了，低头。

Lsxszc：？

题目描述

Lsxszc正在前往xxx市的路上！

为了环保，Lsxszc决定乘电车出行（未成年禁止开车！！！）。

道路可以抽象为一个坐标轴，坐标轴上一共有 $N$ 个充电桩，其中第 $i$ 个充电桩位于坐标 $x_i$ 。

挑剔的Lsxszc希望：

• 因为Lsxszc晕车，所以车辆每天行驶的总距离不得超过 $L$。
• 因为Lsxszc有重度电量焦虑，所以每一天结束时必须停在某个充电站。

特别地，Lsxszc还是一个谨慎的计划执行者，所以希望计算出 $Q$ 个询问的结果，对于每一个询问：

• 给出 $a_i$ 和 $b_i$，要求出在同时满足以上两条要求的前提下，求车辆从第 $a_i$ 个充电站到达第 $b_i$个充电站所需的最少天数。保证 $a_i$ 一定可以到达 $b_i$。

输入格式

$N$

$x_1 \ \ \dots \ \ x_N$

$L$

$Q$

$a_1 \ \ b_1$

$\dots$

$a_Q \ \ b_Q$

输出格式

$Q$ 行，每行为在同时满足两条要求的前提下，车辆从第 $a_i$ 个充电站到达第 $b_i$个充电站所需的最少天数。

输入输出样例 #1

输入 #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 个询问的一种可行方案（记“→”为一天内行驶）：

• 1 → 2（距离 $x_2-x_1=2$）
• 2 → 4（距离 $10$）
• 4 → 7（距离 $6$）
• 7 → 8（距离 $10$） 共 4 天，且每天结束都在某个充电站。

数据范围

• $2 \le N \le 10^5$
• $1 \le L \le 10^9$
• $1 \le Q \le 10^5$
• $1 \le x_1 < x_2 < \cdots < x_N \le 10^9$
• $x_{i+1}-x_i \le L$
• $1 \le a_j,b_j \le N$，且 $a_j \ne b_j$
• 所有输入均为整数

后记

Lsxszc决定下一次找kkkw出题前先环视四周。