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 ith integer denotes the cost, Ci attached to sea hub i.

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

Output

Output the median of the list after the game.

Constraints:

2 ≤ N ≤ 105

2 ≤ Ci ≤ 109, given that Ci is even.

1 ≤ai, bi≤ N

Subtasks

Subtask 1 (50%): 2 ≤ N, Ci ≤ 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
    

Submitting .cpp to 'seagame'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: ABC 218G

Subtask Score
1 50
2 25
3 25
4 0