문제

$N$ 個のキャットタワーがあり，それぞれに $1$ から $N$ までの番号が付けられている．タワー $i$ ($1 \le i \le N$) の高さは $P_i$ である．タワーの高さは $1$ 以上 $N$ 以下の相異なる整数である．$N-1$ 組のタワーが隣接しており，各 $j$ ($1 \le j \le N-1$) について，タワー $A_j$ とタワー $B_j$ が隣接している．はじめ，どのタワーからどのタワーへも隣接するタワーへ移動する操作を繰り返して移動できる．

最初，猫が高さ $N$ のタワーの上にいる．

次に，キャットエクササイズを行う．キャットエクササイズとは，$1$ つのタワーを選んでそこに障害物を置く操作の繰り返しである．ただし，既に障害物を置いたタワーに再び障害物を置くことはできない．操作によって以下のことが起こる．

• 選んだタワーに猫がいない場合，何も起こらない．
• 選んだタワーに猫がおり，かつそれに隣接するタワーすべてに障害物が置かれている場合，キャットエクササイズが終了する．
• いずれでもない場合，障害物が置かれていない隣接するタワーへの移動を繰り返して選んだタワーから移動できるタワーのうち，選んだタワーを除いて最も高いタワーへ，隣接するタワーへの移動を繰り返すことで猫が移動する．このとき，猫は隣接するタワーへの移動の回数が最小になるように移動する．

タワーの高さと隣接するタワーの組の情報が与えられたとき，障害物の置き方を工夫したときの，猫が隣接するタワーへ移動する回数の合計の最大値を求めるプログラムを作成せよ．

입력

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

N
P_1 P_2 \ldots P_N
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}

출력

標準出力に，猫が隣接するタワーへ移動する回数の合計の最大値を $1$ 行で出力せよ．

예제 입력 1

4
3 4 1 2
1 2
2 3
3 4

예제 출력 1

3

以下のようにキャットエクササイズを行ったとき，猫は合計 $3$ 回移動する．

• タワー $1$ に障害物を置く．このとき，猫は移動しない．
• タワー $2$ に障害物を置く．このとき，猫はタワー $2$ からタワー $3$ へ移動し，続いてタワー $3$ からタワー $4$ へと移動する．
• タワー $4$ に障害物を置く．このとき，猫はタワー $4$ からタワー $3$ へと移動する．
• タワー $3$ に障害物を置く．ここでキャットエクササイズが終了する．

猫が $4$ 回以上隣接するタワーへの移動を行うキャットエクササイズの方法は存在しないため，$3$ を出力する．

この入力例は小課題 $1, 2, 3, 4, 5, 7$ の制約を満たす．

예제 입력 2

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

예제 출력 2

7

この入力例は小課題 $4, 6, 7$ の制約を満たす．

제한

• $2 \le N \le 200\,000$．
• $1 \le P_i \le N$ ($1 \le i \le N$)．
• $P_i \ne P_j$ ($1 \le i < j \le N$)．
• $1 \le A_j < B_j \le N$ ($1 \le j \le N-1$)．
• はじめ，どのタワーからどのタワーへも隣接するタワーへ移動する操作を繰り返して移動できる．
• 入力される値はすべて整数である．

서브태스크

1. ($7$ 점) $A_i = i$, $B_i = i + 1$ ($1 \le i \le N-1$), $N \le 16$．
2. ($7$ 점) $A_i = i$, $B_i = i + 1$ ($1 \le i \le N-1$), $N \le 300$．
3. ($7$ 점) $A_i = i$, $B_i = i + 1$ ($1 \le i \le N-1$), $N \le 5\,000$．
4. ($10$ 점) $N \le 5\,000$．
5. ($20$ 점) $A_i = i$, $B_i = i + 1$ ($1 \le i \le N-1$)．
6. ($23$ 점) $A_i = \lfloor \frac{i+1}{2} \rfloor$, $B_i = i + 1$ ($1 \le i \le N-1$)．ただし，$\lfloor x \rfloor$ は $x$ の小数点以下を切り捨てた値を表す．
7. ($26$ 점) 追加の制約はない．