Closest Cities
Contest: Educational Codeforces Round 161 (Rated for Div. 2)
Difficulty rating: 1300
Tags: greedy, implementation, math

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 format:
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 format:
For each query, print one integer — the minimum number of coins you have to spend.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1

Example output:
3
8
1
4
14

Editorial:
Important observation: the answer will not change if you are allowed to move only to adjacent cities. It is true because if you move to a non-adjacent city, you can split the path to that city into parts without increasing its cost. So, the shortest way from $$$x$$$ to $$$y$$$ (consider the case $$$x < y$$$) is to move from city $$$x$$$ to city $$$x+1$$$ for $$$1$$$ coin if it's possible or for $$$a_{x+1} - a_x$$$ if it's not. Then move from city $$$x+1$$$ to city $$$x+2$$$ for $$$1$$$ coin if it's possible, or for $$$a_{x+2} - a_{x+1}$$$ coins if it's not. And so on, until we reach the city $$$y$$$.
Now let's calculate two arrays: $$$l$$$ and $$$r$$$. $$$r_i$$$ is equal to the minimum amount of coins to reach the city $$$i$$$ from city $$$1$$$ (from left to right), $$$l_i$$$ is equal to the minimum amount of coins to reach the city $$$i$$$ from city $$$n$$$ (from right to left). Both of these arrays can be precalculated just like the arrays of prefix sums are calculated. For example, $$$r_1 = 0$$$, $$$r_2 = dist(1, 2)$$$, $$$r_3 = r_2 + dist(2, 3)$$$, $$$r_4 = r_3 + dist(3, 4)$$$ and so on. Here, $$$dist(s, t)$$$ denotes the cheapest way to travel between two adjacent cities $$$s$$$ and $$$t$$$.
Then, the cheapest way between two cities $$$x$$$ and $$$y$$$ can be calculated in the same way as the sum on subarray is calculated for the prefix sum array. There are two cases:
• If $$$x < y$$$ then the answer is $$$r_y - r_x$$$;
• If $$$x > y$$$ then the answer is $$$l_y - l_x$$$;