問題文

頂点に $1$ から $N$ までの番号がついた $N$ 頂点の木 $T$ が与えられます。 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。また、頂点 $i$ には $A_i$ が書かれています。 $i = 1,2,\dots,N$ について以下の問題を解いてください。

• $A_i \leq A_j$ である $j$ ( $1\leq j \leq N$) のうち木 $T$ での $2$ 頂点 $i$, $j$ の距離 $d(i, j)$ の最大値を求めてください。

ここで、木の $2$ 頂点 $i$, $j$ の距離 $d(i, j)$ とは、 $i$ と $j$ を両端点とするパスに含まれる辺の本数です。

制約

• $2 \leq N \leq 2\times 10^5$
• $0 \leq A_i \leq 10^9$
• $1 \leq u_i, v_i \leq N$
• 入力で与えられるグラフは木である
• 入力はすべて整数である

入力

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

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

出力

$i = 1,2,\dots,N$ に対して、答えを空白区切りで出力せよ。

サンプル

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

0 3 2 2 3

6
2 9 1 4 6 8
1 2
1 3
1 4
3 5
3 6

2 0 2 3 3 3