Best City for Hospital

You are given an undirected tree representing a network of n cities connected by roads. The goal is to choose a city for building a hospital such that the maximum distance from the hospital to any other city is minimized.

Formally, let the distance between two cities be the number of roads on the unique simple path connecting them. You need to select a city h such that

$\min_{h \in \{1,2,\ldots,n\}} \; \max_{v \in \{1,2,\ldots,n\}}(d(h,v))$

where \(d(h,v)\) is the distance between cities h and v.

Note: Although additional information about the number of residents in each city is provided, it does not affect the location decision in this problem.

inputFormat

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

1. The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of cities.
2. The second line contains n space-separated integers where the i-th integer denotes the number of residents in city i.
3. Each of the following n - 1 lines contains two integers a and b (1 ≤ a, b ≤ n), representing a bidirectional road between cities a and b.

outputFormat

Output a single integer to standard output (stdout) representing the best city index for locating the hospital according to the criterion described above.

4
3 6 2 4
1 2
2 3
2 4

2