Background

In a hole in the ground there lived a hobbit. Not a nasty, dirty, wet hole, filled with the ends of worms and an oozy smell, nor yet a dry, bare, sandy hole with nothing in it to sit down on or to eat: it was a hobbit-hole, and that means comfort.

—— Opening of The Hobbit

Problem Statement

Brandy Hall is one of the largest hobbit-holes, located inside Buck Hill. It is the ancestral home of the Brandybuck family. For hundreds of years, the hobbits of the Brandybuck family have continuously expanded Brandy Hall until it occupied the entire hill. The Brandybuck family is the maternal family of Frodo Baggins. When he was twelve, his parents unfortunately drowned while boating, and Frodo was taken in to be raised at Brandy Hall.

Brandy Hall has $n$ rooms connected by bidirectional circular passages. It is possible to travel from any room to any other room, but to prevent people from getting lost in the maze of passages, Brandy Hall was carefully designed to ensure that there is exactly one path between any two rooms. In the hot summer, the Brandybucks have a custom of storing sweet and delicious watermelons. Since the watermelons are quite large, the Brandybucks store exactly one watermelon in each room. The most important quality of a watermelon is its sweetness; the sweetness of the watermelon in room $i$ is $a_i$.

Frodo, living there as a guest, can move freely around Brandy Hall and can spend the night in any room he chooses. Every day, Frodo travels from one room to another, but being naturally lazy, he always follows the shortest path. While passing through each room, Frodo can taste the watermelon in that room, or he can choose to ignore it—this also applies to the room he starts in and the room he ends in.

Frodo likes sweet watermelons. However, as everyone knows, the sweetness perceived by taste buds is relative. That is, if Frodo eats a watermelon with sweetness $x$ and then immediately eats a watermelon with sweetness $y$, the taste buds will only perceive the latter as sweet if $y > x$. If $y \le x$, Frodo will not perceive the latter as sweet. Therefore, Frodo set a rule for himself: Except for the first watermelon of the day, the sweetness of every watermelon he eats must be greater than the previous one.

One morning, Frodo suddenly felt weary of the monotonous life in Brandy Hall. Perhaps only watermelons could relieve his boredom. He wants to eat many watermelons without violating his rule. Frodo fell into deep thought... Every day, he faces many choices: which room to start from, which room to end at, which watermelons to eat among the rooms he passes through, and which ones to ignore... Frodo wants to know, given all these choices, what is the maximum number of watermelons Frodo can eat in one day?

Input

The input is read from standard input.

The first line contains a positive integer $n$, representing the number of rooms in Brandy Hall. It is guaranteed that $2 \le n \le 10^{5}$.

The second line contains $n$ positive integers, where the $i$-th integer is $a_i$, representing the sweetness of the watermelon in room $i$. It is guaranteed that $1 \le a_i \le 10^{9}$.

The next $n - 1$ lines describe the structure of Brandy Hall. The $i$-th line contains two positive integers $u_i$ and $v_i$, representing a bidirectional passage between room $u_i$ and room $v_i$. It is guaranteed that $1 \le u_i, v_i \le n$.

Output

The output is written to standard output.

The output consists of a single line containing a positive integer, which is the maximum number of watermelons Frodo can eat in one day.

Examples

Input 1

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

Output 1

5

Note 1

The figure above shows a diagram of Brandy Hall in this example. The black lines represent the passages between rooms; the numbers on the left wall are the room IDs; the numbers inside the watermelons are their sweetness.

Frodo can eat at most 5 watermelons in one day. There are three choices that allow him to eat 5 watermelons:

Choice 1: - Start from room 8 and eat the watermelon (sweetness 1); - Pass through room 6, ignoring the watermelon; - Pass through room 1 and eat the watermelon (sweetness 2); - Pass through room 2 and eat the watermelon (sweetness 4); - Pass through room 4 and eat the watermelon (sweetness 6); - Arrive at room 5 and eat the watermelon (sweetness 7).

Choice 2: - Start from room 8 and eat the watermelon (sweetness 1); - Pass through room 6 and eat the watermelon (sweetness 3); - Pass through room 1, ignoring the watermelon; - Pass through room 2 and eat the watermelon (sweetness 4); - Pass through room 4 and eat the watermelon (sweetness 6); - Arrive at room 5 and eat the watermelon (sweetness 7).

Choice 3: - Start from room 9 and eat the watermelon (sweetness 2); - Pass through room 6 and eat the watermelon (sweetness 3); - Pass through room 1, ignoring the watermelon; - Pass through room 2 and eat the watermelon (sweetness 4); - Pass through room 4 and eat the watermelon (sweetness 6); - Arrive at room 5 and eat the watermelon (sweetness 7).

Examples 2

See ex_2.in and ex_2.ans in the download directory.

Subtasks

This problem has multiple subtasks. Each subtask may contain multiple test cases. You only receive points for a subtask if you pass all test cases within it.

The test cases for each subtask satisfy specific constraints as shown in the table below:

For all test cases, it is guaranteed that $1 \le a_i \le 10^{9}$ and $2 \le n \le 10^{5}$.