Radio Waves

Device connections form a tree, and each frequency is 1, 2, or 3. An edge can carry signals if the absolute difference of its endpoints' frequencies is ≤1, and every edge along a path must be compatible. Find the maximum number of edges between any two devices that can communicate; return 0 if no edge is usable. Adjacent devices with the same frequency are also valid.

输入格式

The first line contains n, the second line contains n frequencies, followed by n−1 lines of 1-based undirected edges. The original raw text gives no upper bound on the number of nodes (the 100,000 in the catalog was added during compilation); this site specifies 1≤n≤100000, the input is a valid tree, and frequencies are 1, 2, or 3.

输出格式

Output the single integer required by the problem.

样例 1

输入：

4
1 3 2 1
1 2
2 3
3 4

输出：

2

样例 2

输入：

1
2

输出：

0

样例 3

输入：

3
1 1 1
1 2
2 3

输出：

2

样例说明

The answers to the three public examples are, in order: 2; 0; 2. The examples were checked by independent enumeration, state search, or direct simulation.