The Bajtowski family has been involved in trade for centuries. The founder of the dynasty, Bajdysław the Great, made a fortune thanks to fluctuations in the prices of hides and furs. More recently, grandfather Bajtosław multiplied the family fortune by importing rare spices from distant lands, and father Bajtazar established a chain of bazaars. Now it is the turn of little Bituś, who has always been fascinated by caravans. You must help him choose two cities between which his first trade route will run.

Bajtocja has $N$ cities, numbered from $1$ to $N$, connected by roads in a tree*. Each city produces a certain type of good, described by the number $t_i$. It is guaranteed that not all cities produce the same good. A trade route must run between two cities that produce different goods (otherwise, there would be no trade). The longer the route, the better, because everyone would like to buy something from far away, even if such a product is available much closer. The caravan will not stop in any cities along the way, so the goods produced there do not matter.

Output the maximum possible length of Bituś's trade route, i.e., the number of roads on that route.

Input

The first line of input contains an integer $N$ ($2 \le N \le 200\,000$) – the number of cities in Bajtocja.

The second line contains $N$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 200\,000$) – the types of goods produced in each city.

The $i$-th of the next $N - 1$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$) – two cities directly connected by a road.

It is guaranteed that there exist two cities with different goods, and that the given pairs $(a_i, b_i)$ describe a tree.

Output

Output a single integer – the maximum possible length of the trade route.

Examples

Input 1

6
1 2 4 4 2 4
5 1
1 2
2 6
1 4
4 3

Output 1

3

Note

The following drawing represents Bajtocja. Large numbers are city numbers, and smaller ones are the types of goods $t_i$.

Bituś can, for example, choose cities 2 and 3, which indeed produce different goods. The length of such a trade route is 3 and it is the maximum possible.

*A tree is defined as a connected undirected graph without cycles.