Cat Tower Exercises

There are (N) cat towers numbered from (1) to (N). Tower (i) has height (P_i), and the heights form a permutation of ({1,2,\ldots,N}). There are (N-1) pairs of adjacent towers such that initially one can travel between any two towers. A cat starts at the tower with height (N).

In the cat exercises, we repeatedly choose a tower (that has not been chosen before) and place an obstacle on it. The process works as follows:

• If the cat is not located at the chosen tower, nothing happens.
• If the cat is at the chosen tower and all towers adjacent to it already have obstacles, the exercise ends.
• Otherwise, from among all towers that can be reached (via adjacent moves avoiding obstacles), the cat moves along the shortest route to the tower with the highest height (excluding its current tower). The number of moves (edges traversed) in this journey is added to a total sum.

The goal is to maximize the total sum of moves made by the cat by choosing the order in which obstacles are placed optimally.

It can be shown that the best strategy makes the cat move in the order of towers with decreasing heights. In other words, if we denote by \(v_h\) the tower with height \(h\), then the maximum sum of moves is \(\sum_{h=2}^{N} d(v_h, v_{h-1})\), where \(d(u,v)\) is the number of moves (edges) on the shortest path in the tree between towers \(u\) and \(v\).

inputFormat

The input begins with an integer (N) on the first line. The second line contains (N) space-separated integers (P_1, P_2, \dots, P_N), which form a permutation of ({1,2,\ldots,N}) and represent the heights of the towers. Each of the next (N-1) lines contains two integers (A_j) and (B_j) ((1 \le j \le N-1)), denoting an edge (adjacency) between tower (A_j) and tower (B_j).

outputFormat

Print a single integer representing the maximum possible sum of the number of moves the cat makes.

sample

2
1 2
1 2

1