問題文

門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下の 2 つの条件を満たすものです。

• $A_1, A_2, A_3$ は全て異なる
• $3$ つの要素の中で $A_2$ が最も大きい、または、$A_2$ が最も小さい

頂点$i$が値$A_i$を持つ木が次を満たすとき、この木は門松木であるといいます。

• 次数 2 以上の 1 つの頂点を$v$、$v$に隣接する2つの頂点を$u,w$($u \neq w$)としたとき、 全ての$u,v,w$について、数列 $A_u, A_v, A_w$ が門松列である
  (どの連続する3頂点$u,v,w$を取り出しても、数列 $A_u, A_v, A_w$ が門松列である、と言い換えてもよい)

不定期に開催される門松木品評会では、木を次のように点数化し評価します。

1. 木が門松木でなかった場合、 0 点とする。
2. 木が門松木であった場合、門松木に含まれる門松列の数をその点数とする。
   次数 2 以上の 1 つの頂点を$v$、$v$に隣接する2つの頂点を$u,w(u \neq w)$として、 数列 $A_u, A_v, A_w$ が門松列になるとき、 頂点の組$\{u,v,w\}$を1つの門松列としてカウントする。 ただし、$\{u,v,w\}$と$\{w,v,u\}$は同一であるとみなし、重複してカウントしない。

かど松さんは木を1つ所有しています。 $N$頂点で、頂点$i$が値$A_i$を持つ木です。
この木の部分木を1つ門松木品評会に出展しようと考えています。
かど松さんが品評会で得られる最大の点数を答えてください。出展できる木は1つだけであることに注意して下さい。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{n-1}$ $y_{n-1}$

1行目に木の頂点数 $N$ が与えられます。
2行目に頂点 $i$ の持つ値 $A_i$ が空白区切りで与えられます。
3行目以降$N-1$行に、辺の情報が与えられます。 $i$番目の辺は頂点$x_i$ と 頂点$y_i$を結ぶ辺です。

入力は全て整数で、以下の制約を満たします。
$1 \leq N \leq 5 \times 10^4$
$1 \leq A_i \leq 10^3$
$1 \leq x_i,y_i \leq N$
$x_i \neq y_i$
木に多重辺や自己ループはなく、連結であることが保証されます。

出力

かど松さんが得られる点数の最大値を出力して下さい。

サンプル

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

4

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

2

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

0