题目描述

Bajtowskich 家族世代从事贸易活动。家族创始人 Bajdysław Wielki 通过皮革和毛皮价格的波动积累了财富。不久前，爷爷 Bajtosław 通过从遥远国家进口稀有香料增加了家族财富，而父亲 Bajtazar 则建立了一个集市网络。现在轮到小 Bituś 了，他一直对商队着迷。你必须帮助他选择两个城市，作为他的第一条贸易路线的起点和终点。

Bajtocja 有 $N$ 个城市，编号从 $1$ 到 $N$，通过道路连接成一棵树。每个城市生产一种商品，用数字 $t_{i}$ 表示。保证并非所有城市生产相同的商品。

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

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

输入格式

输入的第一行包含一个整数 $N$ $(2 \leq N \leq 200000)$，表示拜托西亚的城市数量。

第二行包含 $N$ 个整数 $t_{1}, t_{2}, \ldots, t_{n}$ $(1 \leq t_{i} \leq 200000)$，表示各个城市生产的商品类型。

接下来的 $N-1$ 行中，第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq N)$，表示两个直接通过道路连接的城市。

保证存在至少两个生产不同商品的城市，并且给定的 $(a_{i}, b_{i})$ 对构成一棵树。

输出格式

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

样例

输入

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

输出

3

下图展示了 Bajtocja 的地图。大数字表示城市编号，小数字表示商品类型 $t_{i}$。

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