在名为 Byteville 的村庄里，有 $n$ 座房屋，它们之间由 $n-1$ 条道路连接。任意两座房屋之间都存在唯一的路径。房屋编号从 $1$ 到 $n$。$1$ 号房屋属于村庄管理员 Byteasar。作为“农村地区现代技术赋能框架”的一部分，$n$ 台计算机已被送达 Byteasar 的家中。每座房屋都需要配备一台计算机，分发任务由 Byteasar 完成。Byteville 的居民们已经约定，一旦拿到计算机，就会立即开始玩最新版本的《FarmCraft》游戏。

Byteasar 将所有计算机装上皮卡车，准备出发派送。他携带的汽油刚好够每条道路往返各一次。在每一座房屋，Byteasar 留下一台计算机，然后立即继续他的行程。在每一座房屋，居民们一旦拿到计算机，就会立即开机并安装《FarmCraft》。安装和设置游戏所需的时间很大程度上取决于居民的技术水平，幸运的是，每户人家所需的时间是已知的。在派送完所有计算机后，Byteasar 会回到自己的家中并安装游戏。每条连接两座房屋的道路通行时间恰好为 $1$ 分钟，且（由于居民们急于玩游戏）卸载计算机的时间可以忽略不计。

请帮助 Byteasar 确定一个派送顺序，使得所有 Byteville 的居民（包括 Byteasar）能够尽可能早地一起开始玩游戏。换句话说，找到一个顺序，使得所有人安装完《FarmCraft》的时间点中的最大值最小。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)，表示 Byteville 的房屋数量。第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)，以空格分隔；$c_i$ 表示第 $i$ 号房屋居民安装游戏所需的时间（以分钟为单位）。

接下来的 $n-1$ 行描述了连接房屋的道路。每行包含两个正整数 $a$ 和 $b$ ($1 \le a < b \le n$)，以空格分隔，表示第 $a$ 号房屋和第 $b$ 号房屋之间有一条直接相连的道路。

在总分 $40\%$ 的测试点中，满足 $n \le 7000$。

输出格式

输出的第一行也是唯一一行应包含一个整数：所有居民能够一起玩《FarmCraft》所需的最少分钟数。

样例

输入 1

6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6

输出 1

11

说明

Byteasar 应按以下顺序向房屋派送计算机：$3, 2, 4, 5, 6$ 和 $1$。按房屋编号顺序，游戏安装完成的时间分别为 $11, 10, 10, 10, 8$ 和 $9$ 分钟。因此，所有人可以在 $11$ 分钟后开始玩游戏。

如果 Byteasar 按以下顺序派送游戏：$3, 4, 5, 6, 2$ 和 $1$，则游戏安装完成的时间分别为：$11, 16, 10, 8, 6$ 和 $7$ 分钟。因此，所有人只能在 $16$ 分钟后才能开始玩游戏。