Cat Exercise

There are $N$ cat towers, numbered from $1$ to $N$. The height of Tower $i$ ($1 \le i \le N$) is $P_i$. The heights are distinct integers between $1$ and $N$, inclusive. There are $N-1$ adjacent pairs of towers. For each $j$ ($1 \le j \le N-1$), Tower $A_j$ and Tower $B_j$ are adjacent. At the start, you can travel from any tower to any other tower by moving between adjacent towers.

At the start, a cat stays in the tower of height $N$.

Then we perform cat exercises. In each exercise, we choose a tower and put an obstacle on it. A tower cannot receive a second obstacle. The following happens.

• If the cat is not in the chosen tower, nothing happens.
• If the cat is in the chosen tower and every tower adjacent to it has an obstacle, the cat exercises end.
• Otherwise, the cat moves to the highest tower, excluding its current tower, among the towers it can reach from its current tower without passing through obstacles. It takes the route with the fewest moves between adjacent towers.

Given the tower heights and the adjacency pairs, write a program that finds the maximum possible sum of the cat's moves between adjacent towers when obstacles are placed optimally.

$N$

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

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

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

Print one line containing the maximum possible sum of the cat's moves between adjacent towers.

• $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$).
• At the start, you can travel from any tower to any other tower through adjacent towers.
• All given values are integers.