题目描述

在一层楼有 $n$ 个教室，每个教室的坐标是 $x_i$ 。

$alice$ 是年级纪委，每天需要在楼层巡视年级纪律，他巡视时有以下习惯：

• 他一分钟最多行走不大于 $L$ 的距离。
• 在一分钟内，他一定会以某一个教室为起点，某一个教室为终点（中间路过的教室都当是巡视到了）。

他一天会巡视 $Q$ 次，每次巡视，他会从 $a$ 教室出发，到 $b$ 教室结束 $(a \neq b)$ ，现在他想知道，每次巡视需要花费最少多少分钟。

输入格式

第一行输入一个整数 $n$ 。

第二行输入 $n$ 个整数 $x_1,x_2,...,x_n$ 。

第三行输入一个整数 $L$ 。

第四行输入一个整数 $Q$ 。

接下来 $Q$ 行，每行输入两个整数 $a,b$ 。

输出格式

第 $i$ 行输出第 $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$ 教室巡视到 $8$ 教室，最少需要 $4$ 分钟：

• 第 $1$ 分钟：从 $1$ 教室到 $2$ 教室，走过距离是 $2$ 。
• 第 $2$ 分钟：从 $2$ 教室到 $4$ 教室，走过距离是 $10$ 。
• 第 $3$ 分钟：从 $4$ 教室到 $7$ 教室，走过距离是 $6$ 。
• 第 $4$ 分钟：从 $7$ 教室到 $8$ 教室，走过距离是 $10$ 。

数据范围

对于 $30\%$ 的数据满足： $N\leq 10^3$ , $Q\leq 10^3$ 。

对于 $100\%$ 数据满足：$2\leq N\leq 10^5$ , $1\leq L\leq 10^9$ , $1\leq Q\leq 10^5$ , $1\leq x_1 \lt x_2 \lt \dots \lt x_N \leq 10^9$ , $x_{i+1}-x_i\leq L$ 。

数据保证一定存在最优解。