CF1922C.Closest Cities

There are $n$ cities located on the number line, the $i$-th city is in the point $a_i$. The coordinates of the cities are given in ascending order, so $a_1 \lt a_2 \lt \dots \lt a_n$.

The distance between two cities $x$ and $y$ is equal to $|a_x - a_y|$.

For each city $i$, let's define the closest city $j$ as the city such that the distance between $i$ and $j$ is not greater than the distance between $i$ and each other city $k$. For example, if the cities are located in points $[0, 8, 12, 15, 20]$, then:

• the closest city to the city $1$ is the city $2$;
• the closest city to the city $2$ is the city $3$;
• the closest city to the city $3$ is the city $4$;
• the closest city to the city $4$ is the city $3$;
• the closest city to the city $5$ is the city $4$.

The cities are located in such a way that for every city, the closest city is unique. For example, it is impossible for the cities to be situated in points $[1, 2, 3]$, since this would mean that the city $2$ has two closest cities ($1$ and $3$, both having distance $1$).

You can travel between cities. Suppose you are currently in the city $x$. Then you can perform one of the following actions:

• travel to any other city $y$, paying $|a_x - a_y|$ coins;
• travel to the city which is the closest to $x$, paying $1$ coin.

You are given $m$ queries. In each query, you will be given two cities, and you have to calculate the minimum number of coins you have to spend to travel from one city to the other city.

数轴上有 $n$ 座城市，第 $i$ 座城市位于坐标 $a_i$ 处。城市的坐标按升序给出，即满足 $a_1 \lt a_2 \lt \dots \lt 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$ 个查询。每个查询给出两个城市编号，你需要计算从一座城市到达另一座城市的最小金币花费。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case is given in the following format:

• the first line contains one integer $n$ ($2 \le n \le 10^5$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_1 \lt a_2 \lt \dots \lt a_n \le 10^9$);
• the third line contains one integer $m$ ($1 \le m \le 10^5$);
• then $m$ lines follow; the $i$-th of them contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$), denoting that in the $i$-th query, you have to calculate the minimum number of coins you have to spend to travel from the city $x_i$ to the city $y_i$.

Additional constraints on the input:

• in every test case, for each city, the closest city is determined uniquely;
• the sum of $n$ over all test cases does not exceed $10^5$;
• the sum of $m$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $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 \lt a_2 \lt \dots \lt 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$。

For each query, print one integer — the minimum number of coins you have to spend.

对于每个查询，输出一个整数——你需要花费的最少硬币数量。

Let's consider the first two queries in the example from the statement:

• in the first query, you are initially in the city $1$. You can travel to the closest city (which is the city $2$), paying $1$ coin. Then you travel to the closest city (which is the city $3$) again, paying $1$ coin. Then you travel to the closest city (which is the city $4$) again, paying $1$ coin. In total, you spend $3$ coins to get from the city $1$ to the city $4$;
• in the second query, you can use the same way to get from the city $1$ to the city $4$, and then spend $5$ coins to travel from the city $4$ to the city $5$.

我们考虑题目陈述中的前两个查询：

• 在第一个查询中，你初始位于城市 $1$。你可以前往最近的城市（即城市 $2$），花费 $1$ 枚硬币；接着再次前往最近的城市（即城市 $3$），花费 $1$ 枚硬币；然后再一次前往最近的城市（即城市 $4$），花费 $1$ 枚硬币。总计花费 $3$ 枚硬币，从城市 $1$ 到达城市 $4$；
• 在第二个查询中，你可以采用相同的方式从城市 $1$ 到达城市 $4$，然后额外花费 $5$ 枚硬币从城市 $4$ 前往城市 $5$。