Inversions in a Tree

Input

The first line contains an integer $n$ (1 \leq n \leq 2 \cdot 10^5) — the number of vertices.

The second line contains $n$ integers p_1,p_2,\ldots,p_n (1 \leq p_i \leq n) — the labels. All these numbers are distinct.

Each of the next n-1 lines contains two integers $u$ and $v$ (1 \leq u,v \leq n, u \ne v), describing an edge of the tree.

It is guaranteed that the given graph is a tree.

Output

Print one integer — the maximum possible number of inversions.

Examples

Note

In the first sample, the tree consists of one vertex. There are no inversions, and no operation is possible. Therefore, the answer is $0$.

In the second sample, swap the labels at vertices $1$ and $2$. Then vertex $1$ contains $5$, and all four other vertices contain smaller labels. As vertex $1$ is an ancestor of all of them, there are $4$ inversions. No higher value is possible.

In the third sample, the vertices form the path $1$–$2$–$3$–$4$ with labels 4,3,2,1. Every pair of distinct vertices is an inversion, giving $6$ inversions in total. This is already the maximum for four vertices, so no operation is needed.

Scoring

1. $20$ points — 1 \leq n \leq 10.

2. $30$ points — the tree is a star centered at vertex $1$.

3. $40$ points — the tree is a simple path with vertex $1$ as one of its endpoints.

4. $90$ points — 1 \leq n \leq 3000.

5. $120$ points — no additional constraints.