Optimal Kingdom Capital

In a faraway kingdom, there are n cities connected by roads forming a tree structure. Each city produces a certain number of goods. The total transportation cost when choosing a capital is defined by the formula:

\(Cost = \sum_{i=1}^{n} goods_i \times d(i, capital)\)

Your task is to determine the optimal capital city which minimizes the total transportation cost. In case of a tie, choose the city with the smallest number.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer n representing the number of cities.
2. A line with n space-separated integers representing the number of goods produced by each city (the goods list).
3. n-1 lines, each containing two space-separated integers u and v, indicating that there is a road between cities u and v.

outputFormat

The output is written to standard output (stdout) and is a single integer representing the optimal capital city.

## sample

5
1 2 3 4 5
1 2
2 3
2 4
3 5

3

</p>