311021: CF1922C. Closest Cities

C. Closest Citiestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 < a_2 < \dots < 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.

Input

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 < a_2 < \dots < 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$.

Output

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

ExampleInput

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

Output

3
8
1
4
14

Note

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$.

题目大意：
C. 最接近的城市

有 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 有两个最接近的城市（1 和 3，距离都是 1）。

你可以通过城市旅行。假设你目前在城市 x。那么你可以执行以下操作之一：

- 前往任何其他城市 y，支付 |a_x - a_y| 枚硬币；
- 前往最接近 x 的城市，支付 1 枚硬币。

给你 m 个查询。在每次查询中，你会得到两个城市，你需要计算从一座城市旅行到另一座城市所需的最少硬币数。

输入输出数据格式：
输入：

- 第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。
- 每个测试用例的格式如下：
- 第一行包含一个整数 n（2 ≤ n ≤ 10^5）；
- 第二行包含 n 个整数 a_1, a_2, ..., a_n（0 ≤ a_1 < a_2 < ... < a_n ≤ 10^9）；
- 第三行包含一个整数 m（1 ≤ m ≤ 10^5）；
- 然后是 m 行，每行包含两个整数 x_i 和 y_i（1 ≤ x_i, y_i ≤ n；x_i ≠ 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 到城市 4，通过连续前往最近的城市，共花费 3 枚硬币；第二个查询可以通过同样的方式从城市 1 到城市 4，然后花费 5 枚硬币从城市 4 到城市 5。题目大意： C. 最接近的城市 有 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 有两个最接近的城市（1 和 3，距离都是 1）。 你可以通过城市旅行。假设你目前在城市 x。那么你可以执行以下操作之一： - 前往任何其他城市 y，支付 |a_x - a_y| 枚硬币； - 前往最接近 x 的城市，支付 1 枚硬币。 给你 m 个查询。在每次查询中，你会得到两个城市，你需要计算从一座城市旅行到另一座城市所需的最少硬币数。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。 - 每个测试用例的格式如下： - 第一行包含一个整数 n（2 ≤ n ≤ 10^5）； - 第二行包含 n 个整数 a_1, a_2, ..., a_n（0 ≤ a_1 < a_2 < ... < a_n ≤ 10^9）； - 第三行包含一个整数 m（1 ≤ m ≤ 10^5）； - 然后是 m 行，每行包含两个整数 x_i 和 y_i（1 ≤ x_i, y_i ≤ n；x_i ≠ 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 到城市 4，通过连续前往最近的城市，共花费 3 枚硬币；第二个查询可以通过同样的方式从城市 1 到城市 4，然后花费 5 枚硬币从城市 4 到城市 5。