Bajtocja 拥有 $N$ 座城市，编号从 $1$ 到 $N$，这些城市通过道路连接成一棵树。每座城市生产一种商品，用数字 $t_i$ 表示。题目保证并非所有城市生产的商品都相同。

贸易路线必须在两座生产不同商品的城市之间进行（否则无法进行贸易）。路线越长越好，因为每个人都想从远方购买商品，即使同样的商品在更近的地方也能买到。商队在途中不会在任何城市停留，因此沿途城市生产的商品种类无关紧要。

请输出 Bituś 可以选择的贸易路线的最大长度，即该路径上的道路数量。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 200\,000$)，表示 Bajtocja 的城市数量。

第二行包含 $N$ 个整数 $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 200\,000$)，表示各城市生产的商品种类。

接下来的 $N-1$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le N$)，表示直接相连的两座城市。

题目保证至少存在两座生产不同商品的城市，且给定的 $(a_i, b_i)$ 对构成一棵树。

输出格式

输出一个整数，表示贸易路线的最大可能长度。

样例

输入 1

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

输出 1

3

说明 1

下图展示了 Bajtocja 的结构。大数字为城市编号，括号内的小数字为商品种类 $t_i$。

Bituś 可以选择城市 2 和 3，它们生产的商品确实不同。该贸易路线的长度为 3，是最大可能长度。

注：树定义为连通的无环无向图。