Petrol Stations

There are $n$ cities in the country, some of which are connected by roads. To travel along one road, one tank of gasoline is required. In each city, the cost of a full tank of gasoline is different. Your task is to get from the first city to the $n$-th city with minimum expenses.

Input

The first line contains the number of cities $n(1\le n\le 100)$. The second line contains $n$ numbers, where the $i$-th number represents the cost of gasoline in the $i$-th city (all numbers are integers from $0$ to $100$). The third line contains the number of roads $m$ in the country, followed by the description of the roads. Each road is represented by two numbers — the numbers of the cities it connects. All roads are bidirectional (that is, you can travel in both directions), there is at most one road between any two cities, and there are no roads that lead from a city to itself.

Output

Print a single integer — the minimum cost of the route, or $-1$ if it is impossible to reach the $n$-th city.

Examples