And again trees#12372

And again trees

1 second

256 megabytes

Very hard

Given a root tree with $n$ vertices, where the root is vertex $1$ . Each vertex contains an integer.

We build an array $a$ using the following recursive procedure:

dfs(v):
    write the number in vertex v to the end of array a
    choose any order of the children of vertex v
    for each child u in the chosen order:
        dfs(u)

Initially, $df s (1)$ is called.

Note that the order of children in each vertex can be chosen arbitrarily, so depending on this, the array $a$ can be different.

We will call an element $a_{i}$ a_i a prefix maximum if it is strictly greater than all previous elements of the array. The first element of the array is also considered a prefix maximum.

It is necessary to find the maximum possible number of prefix maxima in the array $a$ .

Input

The first line contains the number $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — the number of vertices in the tree.

The second line contains the array $a$ $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — the values written in the vertices.

In the next $n - 1$ n-1 lines, two numbers $u$ and $v$ $(1 \leq u, v \leq n)$ (1 \le u, v \le n) are given — the edges in the tree.

Output

Output a single number — the maximum possible number of prefix maxima in the array $a$ .

Examples

Example 1

Note

In the first test case, we have the following tree.

After choosing the most advantageous traversal, we will have the following array $[5, 2, 3, 6, 8, 7, 9]$ [5, 2, 3, 6, 8, 7, 9].

The prefix maxima for this array will be $[5, 6, 8, 9]$ [5, 6, 8, 9].

Scoring

Subtask $1$ ( $10$ points): $(n \leq 10)$ (n \le 10)
Subtask $2$ ( $20$ points): $(a_{i} \leq 10)$ (a_i \le 10)
Subtask $3$ ( $30$ points): $(v = u - 1)$ (v = u-1)
Subtask $4$ ( $30$ points): $(u = 1)$ (u = 1)
Subtask $5$ ( $40$ points): $(n \leq 100)$ (n \le 100)
Subtask $6$ ( $50$ points): $(n \leq 500)$ (n \le 500)
Subtask $7$ ( $70$ points): $(n \leq 2000)$ (n \le 2000)
Subtask $8$ ( $80$ points): $(n \leq 75000)$ (n \le 75000)
Subtask $9$ ( $170$ points): No additional constraints