問題文

$N$ 頂点の木があり、各頂点には $1$ から $N$ までの番号が振られています。また、$i\\,(1 \\leq i \\leq N-1)$ 本目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでおり、頂点 $i\\,(1 \\leq i \\leq N)$ には偶数 $A_i$ が書かれています。太郎君と次郎君がこの木と $1$ つの駒を使ってゲームをします。

はじめ、駒は頂点 $1$ に置かれています。二人は太郎君から始めて交互に、駒を現在置かれている頂点と直接辺で結ばれた頂点に移動させます。ただし、駒が一度訪れた頂点に移動させることはできません。駒を移動させることができなくなった時点でゲームが終了します。

太郎君はゲームが終了するまでに駒が訪れた頂点（頂点 $1$ を含む）に書かれた数の（多重）集合の中央値を最大化、次郎君は最小化したいです。両者が最適に行動するとき、駒が訪れた頂点に書かれた数の集合の中央値を求めてください。

中央値とは

大きさ $K$ の数の（多重）集合の中央値は以下のように定義されます。

• $K$ が奇数のとき、小さい方から $\\frac{K+1}{2}$ 番目の値
• $K$ が偶数のとき、小さい方から $\\frac{K}{2}$ 番目の値と $\\frac{K}{2}+1$ 番目の値の平均値

例えば、$\\{ 2,2,4 \\}$ の中央値は $2$ 、$\\{ 2,4,6,6\\}$ の中央値は $5$ です。

制約

• $2 \\leq N \\leq 10^5$
• $2 \\leq A_i \\leq 10^9$
• $A_i$ は偶数
• $1 \\leq u_i < v_i \\leq N$
• 与えられるグラフは木
• 入力は全て整数

入力

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

$N$ $A_1$ $A_2$ $\\ldots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\\vdots$ $u_{N-1}$ $v_{N-1}$

出力

両者が最適に行動するとき、駒が訪れた頂点に書かれた数の（多重）集合の中央値を出力せよ。

入力例 1

5
2 4 6 8 10
4 5
3 4
1 5
2 4

出力例 1

7

両者が最適に行動するとき、ゲームは以下のように進行します。

• 太郎君が駒を頂点 $1$ から頂点 $5$ に移動させる
• 次郎君が駒を頂点 $5$ から頂点 $4$ に移動させる
• 太郎君が駒を頂点 $4$ から頂点 $3$ に移動させる
• 次郎君は駒を動かせないのでゲームが終了する

駒が訪れた頂点に書かれた数の集合は $\\{2,10,8,6\\}$ となるので、中央値である $7$ を出力します。

入力例 2

5
6 4 6 10 8
1 4
1 2
1 5
1 3

出力例 2

8

両者が最適に行動するとき、ゲームは以下のように進行します。

• 太郎君が駒を頂点 $1$ から頂点 $4$ に移動させる
• 次郎君は駒を動かせないのでゲームが終了する

駒が訪れた頂点に書かれた数の集合は $\\{6,10\\}$ となるので、中央値である $8$ を出力します。

入力例 3

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

出力例 3

2