seagame

Po The Sloth wants to sue Potato after the destruction of his property! Fortunately, Potato has managed to strike a deal with Po The Sloth, and must now play a game with him to maximise his profits from his illegal potato plantation!

Po The Sloth has regrown his orchard out at sea, consisting of N sea hubs connected by N-1 bridges between them. Both players start at the sea hub labelled 1. Each sea hub will have a cost C attached to them.

Po The Sloth moves first. On each player's turn, both of them will drive together in Po The Sloth's car to a sea hub that is linked to their current hub by a bridge. To keep things interesting, they are not allowed to drive back to a sea hub they have already visited during the game. Po The Sloth's attorney will note down the cost of the sea hub they visit in a list.

The game ends when neither player can move. At the end of the game, Po The Sloth's attorney will ask Potato to pay an amount equal to the median of the list. (Note that the starting sea hub is included in this list.)

Po The Sloth obviously wants to maximise this median, whereas Potato would like to minimise this median to retain his profits. Help Po The Sloth's attorney determine the median of the list, given that both players play optimally!

Input

The first line contains one integer, N.

The following line contains N integers. The i^th integer denotes the cost, C_i attached to sea hub i.

Each of the next N-1 liness will consist of two integers, a_i and b_i, which denotes the bridge connecting seahub a_i to sea hub b_i.

Output

Output the median of the list after the game.

Constraints:

2 ≤ N ≤ 10⁵

2 ≤ C_i ≤ 10⁹, given that C_i is even.

1 ≤a_i, b_i≤ N

Subtasks

Subtask 1 (50%): 2 ≤ N, C_i ≤ 100

Subtask 2 (25%): Every other sea hub is directly connected to sea hub 1.

Subtask 3 (25%): No other constraints.

Subtask 4 (0%): Sample Testcases

The network of sea hubs and bridges is guaranteed to form a tree.

Sample Input 1:

5
2 4 6 8 10
4 5
3 4
1 5
2 4
    

Sample Output 1:

7
    

Sample Explanation

The game plays as follows:

• Po The Sloth drives from sea hub 1 to 5.
• Potato drives from sea hub 5 to 4.
• Po The Sloth drives from sea hub 4 to 3.
• The game ends, with a median of 7, out of a list consisting of [2, 6, 8, 10]

This testcase is valid for subtasks 1, 3, and 4.

Sample Input 2:

5
6 4 6 10 8
1 4
1 2
1 5
1 3    
    

Sample Output 2:

8
    

Sample Explanation

The game plays as follows:

• Po The Sloth drives from sea hub 1 to 4.
• The game ends, with a median of 8, out of a list consisting of [6, 10]

This testcase is valid for subtasks 1, 2, and 4.

Sample Input 3:

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

Sample Output 3:

2