問題文

$N$ 個の頂点と $N-1$ 本の辺からなる木が与えられます。辺 $i$ ($1 \le i \le N-1$) は頂点 $A_i$ と頂点 $B_i$ を繋いでいます。
各頂点 $i$ ($1 \le i \le N$) には重み $W_i$ が設定されています。

あなたはこの木から辺を $2$ 本選んで (頂点を残して) 削除することで、木を $3$ つに分割します。

それぞれの木について、含まれる頂点の重みの総和を計算します。これを $S_1, S_2, S_3$ とします。
$3$ つの木の重みの差の最大値、すなわち $\max(S_1, S_2, S_3) - \min(S_1, S_2, S_3)$ を最小化してください。

制約

• $3 \le N \le 2 \times 10^5$
• $1 \le W_i \le 10^9$
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• 与えられるグラフは木である。
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

$N$
$W_1\ W_2\ \dots\ W_N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_{N-1}\ B_{N-1}$

$1$ 行目に頂点の数 $N$ 、$2$ 行目に各頂点の重み $W_1, W_2, \ldots, W_N$ 、続く $N-1$ 行に $i$ 番目の辺が頂点 $A_i$ と頂点 $B_i$ を結んでいるという情報が与えられます。

出力

$3$ つの木の重みの (最大値 - 最小値) の最小値を、整数で $1$ 行に出力してください。 最後に改行してください。

サンプル

5
10 10 10 10 10
1 2
2 3
3 4
4 5

10

4
10 5 6 7
1 2
1 3
1 4

9

9
147020957 677362324 450052904 16845359 45810150 325394266 982528921 104391635 490669916
6 2
9 6
4 1
3 2
5 3
2 1
8 3
7 6

625419147