There are n servers in the network arranged in ascending order of their capacity. In the array capacity, the capacity of the ith server is capacity[i], where 0 ≤ i < n.

The distance between two servers, i and j, is defined as the absolute difference in their capacities: /capacity[i] - capacity[j]/. For each server i, the closest server j is the one with the smallest distance to i, and this closest server is unique.

To manage the network, the following operations can be done to server x.

Connect to any server y at a cost of /capacity[x] -capacity[y] / units.

Connect to the closest server of x for a fixed cost of one unit.

Given m queries, each defined by two integers from Server[i] and toServer[i], find the minimum cost required to connect from fromServer[i] to toServer[i] for each query. The connection can be either direct or routed through a server z.

Note:

The values in the capacity array are distinct.

Example

n=3, m=3

capacity = [2, 7, 10]

fromServer = [0, 1, 2]

toServer = [2, 2, 1]

For 0 -> 1, server 1 is closest because |2-7|<|2-10|.

For 1 -> 2, server 2 is closest because |7-10|<|7-2|

For 2 -> 1, server 1 is closest because |10-7|<|10-2|.

Queries:

1. Server 0 to Server 2: Connecting directly would cost |2-10 |=8. It is better to connect through the nearest server two times for 2 units.

2. Server 1 to Server 2: Server 2 is closest to server 1, so a direct connection costs 1.

3. Server 2 to Server 1: Server 1 is closest to server 2, so a direct connection costs 1.

The total costs of all queries are [2, 1, 1].

20

Function Description

23

Complete the function getMinCost in the editor with the following parameter(s):

24

int capacity[n]: the capacity of each server

int fromServer[m]: the starting server

26

int toServer[m]: the ending server

Returns

int[m]: the minimum cost required for each query

Constraints

1≤ n. m<=2*10^5

1 ≤ capacity[i]) ≤ 10^9

0<=fromserver[i],toserver[i]<=n

capacity [] size n = 4

capacity [2, 3, 5, 6]

fromServer [] size m = 3

fromServer = [0, 2, 0]

toServer[] size m = 3

toServer [3,0,1]

Sample Output 0

4

3

1

The closest servers are

0 -> 1 ,1 -> 0 because |2-3| is minimal.

2->3, 3->2, because |5 - 6| is minimal.

Since for 1 -> 2 2 is not closest, connecting them costs | capacity[i] - capacity |[j]| = |5 - 3|

sample test case 2

capacity [] size n = 5
capacity = [2, 5, 6, 9, 11]
fromServer[] size m = 2
fromServer = [2, 1]
toServer[] size m = 2
toServer = [0, 2]

sample output
4
1

3 4 | 9 =11|=2

4 3 |11 - 9| = 2

For 1 -> 0, 0 not closest, so the connection cost is |5 - 2| = 3