Rar the Cat is distributing flyers in order to supplement his income. Instead of distributing flyers at common areas like MRT stations and pet shops, he wants to bribe (or rather give a small reward) to his friends to help him distribute the flyers to their friends.
However, as smart as Rar the Cat is to devise this plan, he does not know how to choose friends to bribe! However, what he does know is how much money is required to bribe each friend, and the friendships between the friends. Therefore, help Rar the Cat calculate which friend is the most worthwhile to bribe. The measurement of worthwhile is calculated by the 'number of cats the flyer is distributed to' (including the one being bribed) divided by the 'cost of bribing the person selected'.
Friends are labelled from 1 to N, up to a total of N friends (if you can't count) and there will be a total of E friendships. In the event where more than 1 friends is the most worthwhile to bribe, output the one with the lower label instead.
The first line of input consist of a single integer, N
The second line of input consists of N integers, with the ith integer being the cost to bribe the ith cat. All the numbers in this line will be positive and fit into a 32-bit signed integer.
The third line of input consist of a single integer, E
The following E lines will contain 2 integers each, A and B. This denotes a friendship between cat A and B. Friendships are known to be mutual and unique (no repeated A and B).
Output a single integer, the label of the friend that is most worthwhile to bribe.
Subtask 1 (18%): 0 < N ≤ 200, 0 ≤ E ≤ 19900.
Subtask 2 (25%): 0 < N ≤ 3000, 0 ≤ E ≤ 300000.
Subtask 3 (57%): 0 < N ≤ 100000, 0 ≤ E ≤ 1000000.
Subtask 4 (0%): Sample Testcases
Due the large amounts of input for this question, we recommend you use scanf/printf instead of cin/cout. A template for inputing and outputting is provided under attachment as well.
Sample Testcase 1
1 2 3 4 5