Minimum Population Difference

You are given \(N\) cities with populations \(p_1, p_2, \dots, p_N\) and a list of existing roads connecting some pairs of cities. A new road may be built between any two cities which are not already directly connected. The cost of building the road is defined as the absolute difference of the populations of the two cities, i.e. \( |p_i - p_j| \). Your task is to compute the minimum possible cost among all pairs of cities.

Note: Although the list of existing roads is provided, it does not affect the result. The answer is determined solely by the populations of the cities.

inputFormat

The input is given in the following format via standard input (stdin):

N
p1 p2 ... pN
M
u1 v1
u2 v2
... 
 uM vM

Where:

• \(N\) is the number of cities.
• \(p1, p2, \dots, pN\) are the populations of the cities.
• \(M\) is the number of existing roads (connections).
• Each of the next \(M\) lines contains two integers \(u\) and \(v\) representing a road connecting city \(u\) and city \(v\).

outputFormat

Output a single integer representing the minimum absolute difference in population between any pair of cities that can be connected by a new road.

5
8 3 6 7 2
4
1 2
1 3
1 4
2 5

1