Building 2

There are $N$ cities in Japan, and they are connected by $N-1$ two-way roads. You can travel from any city to any other city by following some of these roads. Each city has one government office building, and the height of the building in city $i$ is $H_i$.

To welcome athletes from around the world to the International Olympiad in Informatics held in Japan, a sightseeing tour is being planned. A tour starts in one city, moves along roads to other cities, and ends in some city. A city may not be visited more than once.

To make the welcome even more special, some of the government buildings along the tour will be decorated. A designer said that the buildings used for decoration must get taller from the starting city toward the ending city. Let the decorated cities be $i_1, i_2, \ldots, i_k$, visited in that order during the tour. Then $H_{i_1} < H_{i_2} < \cdots < H_{i_k}$ must hold. Not every visited building has to be decorated.

To make the decorations as impressive as possible, you want to use as many buildings as you can. Choose the starting city, the ending city, and the decorated cities freely. Write a program that computes the maximum number of buildings that can be used for decoration.

Read the following input from standard input.

• The first line contains an integer $N$, the number of cities.
• The next $N$ lines contain the building heights. The $i$-th line contains $H_i$, the height of the building in city $i$.
• The next $N-1$ lines contain the roads. The $i$-th line contains two integers $A_i$ and $B_i$ ($1 \le A_i < B_i \le N$), separated by a space. They mean that the $i$-th road connects city $A_i$ and city $B_i$.

Print to standard output one integer, the maximum number of buildings that can be used for decoration.

$2 \le N \le 100000$ (number of cities)

$1 \le H_i \le 1000000000$ (height of the building in city $i$)