問題文

$N$ 頂点からなる木があり、頂点 $i$ $(1 \le i \le N)$ には非負整数 $S_i$ が書かれています。また、辺 $j$ $(1 \le j \le N-1)$ は頂点 $a_j, b_j$ を結んでいます。

この木の頂点から $1$ つを選び、選んだ頂点から始めて次の規則に従って行動することを考えます。ただし、そのときいる頂点を $x$ とします。

• 頂点 $x$ に隣接する頂点の中にまだ訪問したことがない、かつ書かれた整数が $S_x$ より大きい頂点があればそのような頂点から $1$ つを選び、その頂点に移動する。
• もしそのような頂点がなければ、行動を終了する。

行動を終了した時点での、通った頂点（始点と終点を含む）に書かれた整数の和としてあり得る最大値を求めてください。

制約

• $ 1 \le N \le 2 \times 10^5$
• $ 0 \le S_i \le 10^9 (1 \le i \le N)$
• $ 1 \le a_j, b_j \le N (1 \le j \le N-1)$
• 与えられるグラフは木
• 入力はすべて整数

入力

$N$
$S_1$ $S_2$ $\dots$ $S_N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

出力

答えを $1$ 行で出力してください。

サンプル

6
3 1 4 1 5 2
1 2
1 6
2 3
2 4
4 5

6

6
2 5 8 7 0 1
1 2
2 3
2 4
2 5
2 6

15

15
999999986 999999987 999999988 999999989 999999990 999999991 999999992 999999993 999999994 999999995 999999996 999999997 999999998 999999999 1000000000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

14999999895