There are $N$ cities in Japan, connected by $N-1$ bidirectional roads. It is possible to travel between any two cities by following some sequence of roads. Each city has one government office building, and the height of the building in city $i$ is $H_i$.

With the International Olympiad in Informatics being held in Japan, we are planning a sightseeing tour to welcome athletes from around the world. A sightseeing tour starts at a certain city, repeatedly moves to a different city by following roads, and ends at a certain city. During this process, no city is visited more than once.

To welcome the athletes even more warmly, we have decided to decorate some of the government office buildings in the cities visited during the tour. A famous designer was consulted, and they stated that the buildings used for decoration must increase in height from the starting city to the destination city. In other words, if we denote the cities whose buildings are to be decorated as $i_1, i_2, \dots, i_k$ in the order they are visited during the tour, the heights of the buildings must satisfy $H_{i_1} < H_{i_2} < \dots < H_{i_k}$. (Note that it is not required to decorate the buildings of all visited cities.)

Task

To make the decorations as spectacular as possible, we want to maximize the number of buildings used for decoration. Write a program that calculates the maximum number of buildings that can be used for decoration, given that the starting city, the destination city, and the cities to decorate can be chosen freely.

Constraints

$2 \le N \le 100\,000$ $1 \le H_i \le 1\,000\,000\,000$

Input

Read the following from standard input:

• The first line contains an integer $N$, representing the number of cities.
• The next $N$ lines provide information about the height of the government office building in each city. The $i$-th line of these contains an integer $H_i$, representing the height of the building in city $i$.
• The next $N-1$ lines provide information about the roads. The $i$-th line of these contains two space-separated integers $A_i, B_i$ ($1 \le A_i < B_i \le N$), representing that the $i$-th road connects city $A_i$ and city $B_i$.

Output

Output a single integer representing the maximum number of buildings that can be used for decoration.

Subtasks

1. 10% of the points are awarded for test cases where $N \le 100$.
2. 30% of the points are awarded for test cases where $N \le 2\,000$.

Examples

Input 1

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

Output 1

4