C. 最近的城市

时间限制：每个测试 $2$ 秒
内存限制：每个测试 $256$ MB

数轴上有 $n$ 个城市，第 $i$ 个城市位于坐标 $a_i$ 处。城市的坐标按升序给出，因此 $a_1 < a_2 < \dots < 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$ 有两个最近的城市（$1$ 和 $3$，距离均为 $1$）。

你可以在城市之间旅行。假设你当前在城市 $x$，你可以执行以下两种操作之一：

• 前往任意其他城市 $y$，花费 $|a_x - a_y|$ 枚硬币；
• 前往距离 $x$ 最近的城市，花费 $1$ 枚硬币。

现在给你 $m$ 个询问。在每个询问中，给定两个城市，你需要计算从其中一个城市到达另一个城市所需花费的最少硬币数量。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的格式如下：

• 第一行包含一个整数 $n$（$2 \le n \le 10^5$）；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_1 < a_2 < \dots < a_n \le 10^9$）；
• 第三行包含一个整数 $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$。你可以先前往最近的城市（即城市 $2$），花费 $1$ 枚硬币。然后再前往最近的城市（即城市 $3$），再花费 $1$ 枚硬币。接着再前往最近的城市（即城市 $4$），再花费 $1$ 枚硬币。总共花费 $3$ 枚硬币从城市 $1$ 到达城市 $4$。
• 在第二个询问中，你可以用同样的方式从城市 $1$ 到达城市 $4$，然后花费 $5$ 枚硬币从城市 $4$ 直接前往城市 $5$。