问题陈述

有一个根为顶点1的树，有N个顶点。对于每个$i = 1, 2, \ldots, N-1$，第i条边连接顶点$u_i$和顶点$v_i$。除了根以外的每个顶点上都写有一个正整数：对于每个$i = 2, 3, \ldots, N$，顶点$i$上写的整数是$A_i$。高桥和青木将使用这棵根树和一个棋子进行以下对抗性游戏：

棋子从顶点1开始。在游戏结束之前，他们重复以下步骤：

1. 首先，青木选择一个非根顶点，并将该顶点上写的整数替换为0。
2. 接下来，高桥将棋子移动至该棋子所在顶点的(直接)子节点上。
3. 然后，如果棋子在叶子节点上，游戏结束。即使不是这种情况，高桥也可以选择立即结束游戏。

游戏结束时，高桥的得分将是棋子当前所在顶点上写的整数。高桥希望尽可能使自己的得分最大，而青木希望尽可能使得分最小。请输出当双方都为了各自目的最优地进行游戏时，高桥将得到的分数。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq u_i, v_i \leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

输入从标准输入中按以下格式给出：

$N$ $A_2$ $\ldots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$

输出

输出答案。

示例输入1

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

示例输出1

5

当双方都为了各自目的最优地进行游戏时，可能的游戏进展如下：

1. 棋子从顶点1开始。
2. 青木将顶点7上的整数从10改为0。
3. 高桥将棋子从顶点1移到顶点2。
4. 青木将顶点4上的整数从6更改为0。
5. 高桥将棋子从顶点2移到顶点5。
6. 高桥选择结束游戏。

游戏结束时，棋子位于顶点5上，此时写有整数5，因此高桥的分数将为5。

示例输入2

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

示例输出2

70