Hide

Problem F
Hermits

In this modern world, people are moving into more and more tightly packed cities. This is a development that the hermits of the world love – if people concentrate in cities, that leaves much more space for hermits! Well, a development that almost all hermits love. Hermiticism is a calling that can develop in anyone, even those who like getting their morning gourmet coffee from urban luxury cafés. This restricts the urban hermit to locations in cities where not too many people live.

One of those hermits, Urban, is planning a move to Stockholm. He has already identified what city district he wants to move to. The district consists of $N$ different streets.

After buying his morning coffee, Urban likes taking solitary morning walks up and down the street he lives on. This means that he wants to pick a street that not too many people live on, but also one that not too many busy streets cross. More formally, each street $i$ has a number $a_ i$ of people that live on it. Urban wants to live on a street where the total number of people who live on the street and all streets that cross it is minimal, which he thinks is the quietest street. Can you help him find which one it is?

Input

The first line contains an integer $N$ ($2 \le N \le 1\, 000$), the number of streets in the district. The next line contains the $N$ integers $a_1, \dots , a_ N$ ($1 \le a_ i \le 10^6$), the number of people who lives on the streets.

The next line contains the number of pairs of streets that cross $M$ ($1 \le M \le \frac{N(N - 1)}{2}$). The following $M$ lines each contain the one-based indices of two streets that cross each other. The streets are numbered in the same order as the $a_ i$.

Output

Output a single integer – the number of the quietest street. If there are several quietest streets, he prefers the one with the lowest index.

Sample Input 1 Sample Output 1
3
1 2 3
1
2 1
1
Sample Input 2 Sample Output 2
3
1 2 3
1
3 1
2

Please log in to submit a solution to this problem

Log in