問題文

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

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

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

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

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

制約

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

小課題

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

入力例 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 の制約を満たす．