你将去探索一个充满美丽珠子的洞穴。洞穴由 $n$ 个房间组成，编号为 $1, 2, \dots, n$，通过 $(n - 1)$ 条双向隧道连接，形成一棵树。在第 $i$ 个房间里，恰好有一颗颜色为 $c_i$ 的珠子。

这个洞穴不属于你，因此你的行动受到限制。在进入洞穴之前，你需要选择两个房间 $x$ 和 $y$（可能 $x = y$），并向主人提交申请。然后，你可以从第 $x$ 个房间进入洞穴，并沿着从第 $x$ 个房间到第 $y$ 个房间的最短路径行走。每当你访问一个新房间时（包括第一个房间 $x$ 和最后一个房间 $y$），你可以选择是否拾取该房间里的珠子。最后，你需要将你拾取的所有珠子按照拾取的顺序连接成一个字符串。你必须确保该字符串是回文的，否则你将无法把这些珠子带回家。注意，一个字符串是回文的，当且仅当它从左向右读和从右向左读是一样的。

你希望使这个回文字符串尽可能长。你能带走珠子的最大数量是多少？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示房间的数量。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$)，表示每个房间中珠子的颜色。保证每种颜色最多出现两次。 接下来的 $(n - 1)$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示第 $u_i$ 个房间和第 $v_i$ 个房间之间的一条双向隧道。保证这些道路构成一棵树。

输出格式

输出一行，包含一个整数，表示你能带走珠子的最大数量。

样例

样例输入 1

4
1 1 2 2
1 2
2 3
2 4

样例输出 1

3

样例输入 2

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

样例输出 2

4