F. 无产阶级万岁
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

你是无产阶级战士，并且立志要把资本家挂到路灯上。

现在你打算给底层工人发放福利。但是你不想工人们因为福利不均而打起来。

这个公司也非常神奇，底层工人只有同时在同一个资本家的支配下才能互相联系，了解到对方的情况。

现在每个底层工人都有一个期望福利，你想满足他们所有的愿望，但是如果分配的福利差距太大的话，可能会引起不满，显然如果无法知晓对方情况的话，就不会打起来。

你现在有两种操作避免这种情况的发生。

  • 制定非负数$$$x$$$的标准
  • 选择一个资本家挂在路灯上，这样会有一些底层员工失去联系。

可惜的是，你只有一个路灯了，求一个最小的非负数 $$$x$$$。

形式化的， 给定一棵$$$n$$$个节点的无向的树，只有叶子节点有一个点权$$$ai$$$，不允许两个联通的叶子点权之差大于$$$x$$$，你现在有一个删去一个节点的操作（即删去这个点和与其相连的边使其变为一个森林），求最小的$$$x$$$.

$$$3 \le n \le 10^5$$$

叶子数量 $$$\le 500$$$

点权大小即$$$a_i \le 10^5$$$

特别的，数据保证$$$1$$$不为叶子节点,您可以放心将他当作根节点，根节点不当作叶子节点。

Input

第一行一个数$$$n$$$表示有$$$n$$$个底层工人和资本家

第二行有$$$n$$$个整数，如果是$$$0$$$则是资本家，如果不是$$$0$$$则代表第i号底层工人的期望福利

第三行到第$$$n+2$$$行，每行有两个整数$$$u$$$，$$$v$$$表示$$$uv$$$存在领导和被领导的关系。

Output

一个整数$$$x$$$

Example
Input
10
0 0 37 15 0 22 20 0 4 7
1 2
1 8
2 3
2 4
1 5
5 6
5 7
8 9
8 10
Output
18