L. LIS on Tree
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes. Each node has a non-negative integer value $$$v_i$$$.

Let a tree subsequence be a sequence of nodes $$$S = s_1, s_2, \dots s_k$$$ such that there exists vertices $$$u, v$$$ in the tree such that $$$S$$$ is a subsequence of the unique shortest path starting at $$$u$$$ and ending at $$$v$$$.

A tree subsequence is increasing if for all $$$1 \leq i \leq k - 1$$$ we have that $$$v_{s_i} \lt v_{s_{i + 1}}$$$ (Note that this corresponds to a strictly increasing sequence).

Find the length of the longest increasing tree subsequence.

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$) — the number of nodes in the tree.

The second line of input contains $$$n$$$ integers $$$v_1, v_2, \cdots, v_n$$$ ($$$1 \leq v \leq 10^{9}$$$) — the value of each node in the tree.

The following $$$n - 1$$$ lines each contain two integers $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$)— the endpoints of edge $$$i$$$.

It is guaranteed that the given edges form a tree.

Output

Output a single integer — the length of the longest increasing tree subsequence.

Examples
Input
4
7 7 7 7
2 4
2 3
1 2
Output
1
Input
5
3 9 14 7 12
1 4
3 4
4 5
2 3
Output
3
Input
12
10 3 8 13 6 2 3 14 1 5 10 6
1 10
2 6
2 10
7 9
2 9
9 11
3 7
2 8
5 7
4 7
2 12
Output
4