Migrated from Lutece 2586 The Number of Procedures

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a directed tree with the root 1. All the nodes have an initial value $a$ of DFS order.

After calling dfs(1) the following algorithm returns $a$ as a DFS order of a tree rooted at $1$ :

order := 0
a := array of length n 

function dfs(u):
    order := order + 1
    a[u] := order
    for all v such that there is a directed edge (u -> v):
        dfs(v)

Note that there may be different DFS orders for a given tree.

After that, we will perform some procedures on the tree. One procedure is as follows.

• Among all directed edges $u\to v$ such that $a_u<a_v$, select the edge $u'\to v'$ with the lexicographically smallest pair $(a_{u'},a_{v'})$.
• Swap $a_{u'}$ and $a_{v'}$ .

You will get the final value $a$ of each node. Your task is to answer how many procedures are performed on the tree.

Input

The first line of the input contains an integer $n$ — the number of nodes on the tree.

The second line contains n integers $a_1,a_2,\ldots ,a_n$ — the current vlaue of the tree.

Each of the next $n-1$ lines contains two integers $u_i,v_i\ (u_i\neq v_i)$, describing a directed edge from $u_i$ to $v_i$. The edges form a directed tree rooted at 1.

Output

One integer, the number of procedures.

Samples

7
4 5 2 1 7 6 3
1 5
7 6
1 2
2 7
3 4
1 3

5

Constraints

$1\le n \le 100000$ $1\le a_i,u,v\le n$

Note

The picture is changed as the sample run.

Resources

2021 UESTC ICPC Training for Graph