Background

在一条线上有 $n$ 座城市，其中第 $i$ 座城市的位置是 $a_{i}$，两座城市$x$,$y$之间的距离为$|a_{x} - a_{y}|$。 我们定义如果城市 $i$ 到城市 $j$ 的距离小于由城市 $i$ 到其他任何一座城市的距离，那么， $j$ 是 $i$ 的最近的城市，例如，如果城市位于点$[0,8,12,15,20]$:

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

在这一城市排列的规律下，每座城市的最近的城市都是唯一的，如不可能存在城市分布于$[1,2,3]$的情况，因为这样城市2同时拥有两个最近的城市1和3。

你现在正在各个城市之间旅行。如果你此刻位于城市$x$，你可以执行以下操作之一：

• 前往任何其他城市 𝑦 ，支付 $|a_{x} - a_{y}|$ 枚金币；
• 前往城市 $x$ 的最近的城市，支付 1 枚金币。

你会收到 𝑚 个询问。在每个查询中，你将得到两个城市，请你计算从一个城市到另一个城市所需的最少金币数。

Input

第一行包含一个整数 𝑡 ( 1 $≤$ 𝑡 $≤$ $10^4$ ) - 测试用例的数量。

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

• 第一行包含一个整数 𝑛 ( 2 $≤$ $n$ $≤$ $10^5$ )；
• 第二行包含 𝑛 个整数 $a_{1},a_{2}......a_{n}$,(0 ≤$a_{1}$<$a_{2}$<⋯<$a_{n}$≤ $10^9$);
• 第三行包含一个整数 𝑚 (1≤𝑚≤$10^5$ );
• 接下来的𝑚 行；其中第 𝑖 行包含两个整数 $x_{i}$ 和 $y_{i}$ ( 1≤$x_{i}$,$y_{i}$≤𝑛 ；$x_{i}$ $≠$ $y_{i}$)，表示在第 $i$ 次查询中，你必须计算从城市 $x_{i}$ 到城市 $y_{i}$ 所需要花费的最少金币数。

输入的其他限制

• 在每个测试案例中，对于每个城市，其最近的城市是唯一确定的；
• 所有测试用例中 𝑛 的总和不超过 $10^5$；
• 所有测试用例中 𝑚 的总和不超过 $10^5$ 。

Output

对于每个查询，打印一个整数 —— 必须花费的最少金币数。

Samples

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

3
8
1
4
14

Limitation

2s, 256 megabytes for each test case.

From

Educational Codeforces Round 161 ，C题