虽然因赞恩成功找到了他心爱的骨头,但他的主人赞恩却还没有回来。为了寻找赞恩,他需要很多钱,但遗憾的是他没有。为了解决这个问题,他决定入侵银行。
有 n 个组,编号从 1 到 n。还有 n - 1 根电线连接各组。所有银行最初都是在线的。每个银行也有其初始强度:银行 i 的初始强度为 ai。
在继续之前,让我们定义一些关键字。当且仅当存在直接连接银行 i 和银行 j 的电线时,银行 i 和银行 j 是相邻的。银行i和银行j是半相邻的当且仅当存在网上银行k使得银行i和银行k相邻并且银行k和银行j相邻。
当一家银行被黑客攻击时,它会离线(并且不再在线),并且与其相邻或半相邻的其他银行的强度增加 1。
为了开始他的计划,Inzane 将首先选择一家银行进行黑客攻击。确实,这样的银行的实力绝对不能超过他电脑的实力。此后,他将反复选择接下来要攻击的银行,直到所有银行都被攻击为止,但当且仅当满足所有这些条件时,他才能继续攻击银行x:
1. 银行 x 上线。也就是说,银行 x 还没有被黑客入侵。
2. 银行 x 与某离线银行相邻。
3. 银行 x 的强度小于或等于 Inzane 计算机的强度。
确定 Inzane 破解所有银行所需的最低计算机强度。
输入
第一行包含一个整数 n (1 ≤ n ≤ 3·105) — 存储体总数。
第二行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 银行的实力。
接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 意味着有一条电线直接连接组 ui 和 vi。
保证电线以这样的方式连接银行,Inzane 可以使用具有适当强度的计算机以某种方式破解所有银行。
输出
打印一个整数——Inzane 完成目标所需的最低计算机强度。
示例
输入 #1
5 1 2 3 4 5 1 2 2 3 3 4 4 5
输出 #1
5
输入 #2
7 38 -29 87 93 39 28 -55 1 2 2 5 3 2 2 4 1 7 7 6
输出 #2
93
输入 #3
5 1 2 7 6 7 1 5 5 3 3 4 2 4
输出 #3
8
注意
在第一个示例中,Inzane 可以使用强度为 5 的计算机入侵所有银行。具体方法如下:
- 最初,银行的优势为 [1, 2, 3, 4, 5]。
- 他黑掉了银行5,然后银行的优势变成了[1, 2, 4, 5, - ]。
- 他黑掉了银行4,然后银行的优势变成了[1, 3, 5, - , - ]。
- 他黑掉了银行3,然后银行的优势变成了[2, 4, - , - , - ]。
- 他黑掉了银行2,然后银行的优势变成了[3, - , - , - , - ]。
- 他通过侵入 1 号银行来完成他的目标。
在第二个示例中,Inzane 可以按顺序攻击银行 4、2、3、1、5、7 和 6。这样,他就可以使用强度为 93 的计算机入侵所有银行。