고양이 운동

고양이 타워가 $N$개 있고, 1번부터 $N$번까지 번호가 붙어 있습니다. $i$번 타워의 높이는 $P_i$입니다. 타워의 높이는 1 이상 $N$ 이하의 서로 다른 정수입니다. 인접한 타워 쌍은 $N-1$개이며, $j$번째 쌍은 타워 $A_j$와 타워 $B_j$입니다. 처음에는 인접한 타워를 따라 이동해서 어떤 타워에서든 다른 모든 타워로 갈 수 있습니다.

처음에 고양이는 높이가 $N$인 타워에 있습니다.

그다음 고양이 운동을 진행합니다. 운동에서는 타워를 하나 골라 장애물을 놓습니다. 이미 장애물이 놓인 타워에는 다시 놓을 수 없습니다. 이때 다음 일이 일어납니다.

• 고양이가 선택한 타워에 있지 않으면 아무 일도 일어나지 않습니다.
• 고양이가 선택한 타워에 있고, 그 타워에 인접한 모든 타워에 장애물이 놓여 있으면 고양이 운동이 끝납니다.
• 그 밖의 경우에는 장애물이 없는 타워 중에서 인접한 타워를 따라 도달할 수 있는 곳 가운데, 현재 타워를 제외하고 가장 높은 타워로 고양이가 이동합니다. 이때 인접한 타워 사이의 이동 횟수가 가장 적은 경로를 택합니다.

타워 높이와 인접 관계가 주어졌을 때, 장애물을 적절히 놓아 고양이가 인접한 타워로 이동한 횟수의 합을 최대로 만들 수 있는 값을 구하는 프로그램을 작성하세요.

$N$

$P_1$ $P_2$ $\cdots$ $P_N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{N-1}$ $B_{N-1}$

고양이가 인접한 타워로 이동한 횟수의 합의 최댓값을 한 줄에 출력합니다.

• $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$).
• 처음에는 인접한 타워를 따라 어떤 타워에서든 다른 모든 타워로 갈 수 있습니다.
• 주어지는 모든 값은 정수입니다.