Crazy Bobo

Problem Description

Bobo has a tree,whose vertices are conveniently labeled by 1,2,...,n.Each node has a weight $w_i$. All the weights are distrinct. A set with m nodes ${v_1,v_2,...,v_m}$ is a Bobo Set if:

• The subgraph of his tree induced by this set is connected.
• After we sort these nodes in set by their weights in ascending order,we get ${u_1,u_2,...,u_m}$,(that is,$w_{u_i} < w_{u_{i+1}}$ for i from 1 to m-1).For any node $x$ in the path from $u_i$ to $u_{i+1}$(excluding $u_i$ and $u_{i+1}$),should satisfy $w_x < w_{u_i}$. Your task is to find the maximum size of Bobo Set in a given tree.

Input

The input consists of several tests. For each tests: The first line contains a integer n ($1 \leq n \leq 500000$). Then following a line contains n integers $w_1,w_2,...,w_n$ ($1 \leq w_i \leq 10^9$,all the $w_i$ is distrinct).Each of the following n-1 lines contain 2 integers $a_i$ and $b_i$,denoting an edge between vertices $a_i$ and $b_i$ ($1 \leq a_i,b_i \leq n$). The sum of n is not bigger than 800000.

Output

For each test output one line contains a integer,denoting the maximum size of Bobo Set.

Sample Input

7
3 30 350 100 200 300 400
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output

5

Author

ZSTU

Source

2015 Multi-University Training Contest 3