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 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:
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.
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:
Additional constraints on the input:
For each query, print one integer — the minimum number of coins you have to spend.
150 8 12 15 2051 41 53 43 25 1
3 8 1 4 14
Let's consider the first two queries in the example from the statement:
Name |
---|