题目描述

数轴上有 $n$ 座城市，其中第 $i$ 座城市在 $a_{i}$ 点，且城市坐标按升序给定，即 $a_{1} < a_{2} < ... < a_{n}$ 。

城市 $x$ 和 $y$ 的距离记为 | $a_{x} - a_{y}$ | 。

对于第 $i$ 座城市，定义离它最近的城市 $j$ 为离它最近的城市的条件是城市 $i$ 和 $j$ 之间的距离不超过城市 $i$ 到任意其他城市 $k$ 的距离。例如，对于 [ 0 , 8 , 12 , 15 , 20 ] 这样一组城市来说：

• 离城市 1 最近的城市是城市 2 ；
• 离城市 2 最近的城市是城市 3 ；
• 离城市 3 最近的城市是城市 4 ；
• 离城市 4 最近的城市是城市 3 ；
• 离城市 5 最近的城市是城市 4 ；

这组城市的位置满足一个城市有且仅有一个距离最近的城市。例如，城市组 [ 1 , 2 , 3 ] 的位置是不合法的，因为城市 2 有两个距离最近的城市（城市 2 距离城市 1 和 3 的距离都是 1 ）。

假设你现在城市 $x$ ，你有 2 种出行方式：

• 花费 | $a_{x} - a_{y}$ | 枚硬币到达任意一座城市 $y$ ；
• 花费 1 枚硬币到达距离 $x$ 最近的城市。

现给定 $m$ 次询问。在每次询问中，你会被给定两座城市并计算从其中一座到另一座所要花费的最少硬币数。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示数据组数。

每组数据输入形式如下：

• 第一行包含一个整数 $n$ ($2 \le \le 10^5$);
• 第二行包含 $n$ 个整数 $a_{1} , a_{2} , ... , a_{n} ( 0 \le a_{1} < a_{2} < ... a_{n} \le 10^4 )$ ;
• 第三行包含一个整数 $m$ ($1 \le m \le 10^5$)
• 接下来 $m$ 行中，第 $i$ 行包含两个整数 $x_{i}$ 和 $y_{i} ( 1 \le x_{i} , y_{i} \le n ; x_{i} \ne y_{i} ) $ ，表示第 $i$ 次询问要计算城市 $x_{i}$ 和 $y_{i}$ 之间旅行的最小花费。

额外的数据限制：

• 在每一组数据中，距离每一座城市最近的城市是唯一确定的；
• 所有数据中的 $n$ 之和不超过 $10^5$ ;
• 所有数据中的 $m$ 之和不超过 $10^5$ 。

输出格式

对于每次询问，输出你要在这两座城市之间进行城际旅行所需要的最小硬币数。

1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1

3
8
1
4
14

提示

下面让我们以前两组询问为例进行样例解释：

• 对于第一次询问，你初始在城市 1 。你可以花费 1 枚硬币到达距离最近的城市（城市 2 ），接下来再花一枚硬币到距离最近的城市（城市 3 ），最后再花一枚硬币到达最近的城市（城市 4 ）。这样，你花费了 3 枚硬币从城市 1 到城市 4 。
• 对于第二次询问你可以以同样的方式从城市 1 到城市 4 ，然后再花费 5 枚硬币从城市 4 到城市 5 。