CF796C.Bank Hacking

Although Inzane successfully found his beloved bone, Zane, his owner, has yet to return. To search for Zane, he would need a lot of money, of which he sadly has none. To deal with the problem, he has decided to hack the banks.

There are n banks, numbered from 1 to n. There are also n - 1 wires connecting the banks. All banks are initially online. Each bank also has its initial strength: bank i has initial strength a__i.

Let us define some keywords before we proceed. Bank i and bank j are neighboring if and only if there exists a wire directly connecting them. Bank i and bank j are semi-neighboring if and only if there exists an online bank k such that bank i and bank k are neighboring and bank k and bank j are neighboring.

When a bank is hacked, it becomes offline (and no longer online), and other banks that are neighboring or semi-neighboring to it have their strengths increased by 1.

To start his plan, Inzane will choose a bank to hack first. Indeed, the strength of such bank must not exceed the strength of his computer. After this, he will repeatedly choose some bank to hack next until all the banks are hacked, but he can continue to hack bank x if and only if all these conditions are met:

1. Bank x is online. That is, bank x is not hacked yet.
2. Bank x is neighboring to some offline bank.
3. The strength of bank x is less than or equal to the strength of Inzane's computer.

Determine the minimum strength of the computer Inzane needs to hack all the banks.

尽管因赞成功找到了他心爱的骨头，但他的主人扎恩却仍未归来。为了寻找扎恩，他需要大量资金，而他遗憾地一无所有。为解决这一问题，他决定入侵银行。

共有 $n$ 家银行，编号从 $1$ 到 $n$。此外还有 $n-1$ 根导线连接这些银行。所有银行初始均处于在线状态。每家银行还具有其初始强度：银行 $i$ 的初始强度为 $a_i$。

在继续之前，我们先定义若干关键词：当且仅当存在一根导线直接连接银行 $i$ 和银行 $j$ 时，称银行 $i$ 与银行 $j$ 是相邻的；当且仅当存在一家在线银行 $k$，使得银行 $i$ 与银行 $k$ 相邻，且银行 $k$ 与银行 $j$ 相邻时，称银行 $i$ 与银行 $j$ 是半相邻的。

当一家银行被入侵后，它将变为离线状态（即不再在线），而所有与之相邻或半相邻的其他银行的强度均增加 $1$。

为启动该计划，因赞将首先选择一家银行进行入侵。事实上，该银行的强度不得超过他计算机的强度。此后，他将不断选择下一家银行进行入侵，直至所有银行均被入侵完毕；但他只有在满足以下全部条件时，才可继续入侵银行 $x$：

1. 银行 $x$ 处于在线状态，即尚未被入侵；
2. 银行 $x$ 与某家已离线的银行相邻；
3. 银行 $x$ 的强度小于或等于因赞计算机的强度。

请确定因赞为入侵全部银行所需的计算机的最小强度。

The first line contains one integer n (1 ≤ n ≤ 3·105) — the total number of banks.

The second line contains n integers _a_1, _a_2, ..., a__n ( - 109 ≤ a__i ≤ 109) — the strengths of the banks.

Each of the next n - 1 lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — meaning that there is a wire directly connecting banks u__i and v__i.

It is guaranteed that the wires connect the banks in such a way that Inzane can somehow hack all the banks using a computer with appropriate strength.

第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）——银行的总数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \leq a_i \leq 10^9$）——各银行的强度。

接下来的 $n-1$ 行中，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$）——表示银行 $u_i$ 与银行 $v_i$ 之间有一根直接连接的网线。

保证这些网线将银行连接成一种结构，使得 Inzane 能够借助一台具备适当强度的计算机成功入侵所有银行。

Print one integer — the minimum strength of the computer Inzane needs to accomplish the goal.

输出一个整数——Inzane 为实现目标所需的计算机的最小运算能力。

In the first sample, Inzane can hack all banks using a computer with strength 5. Here is how:

• Initially, strengths of the banks are [1, 2, 3, 4, 5].
• He hacks bank 5, then strengths of the banks become [1, 2, 4, 5,  - ].
• He hacks bank 4, then strengths of the banks become [1, 3, 5,  - ,  - ].
• He hacks bank 3, then strengths of the banks become [2, 4,  - ,  - ,  - ].
• He hacks bank 2, then strengths of the banks become [3,  - ,  - ,  - ,  - ].
• He completes his goal by hacking bank 1.

In the second sample, Inzane can hack banks 4, 2, 3, 1, 5, 7, and 6, in this order. This way, he can hack all banks using a computer with strength 93.

在第一个样例中，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 的计算机攻破所有银行。