Problem Statement

NOTE: This problem is the same as Treason with different constraints.

You are given a connected graph with ~n~ nodes and ~n - 1~ edges.

Each node in your graph represents a biome in Minecraft. There are many biomes, and lots of them represent different seasons. We have simplified it such that there are only four seasons.

Each node in your graph has a single season associated with it (a number from ~1~ to ~4~).

Determine the longest distance between the two nodes with different seasons.

Input Format

Your first line will contain a single integer ~n~. Your next line will contain ~n~ space-separated integers, the ~i^{th}~ integer represents the season of the ~i^{th}~ node. Your next ~n - 1~ lines will contain two integers each, ~u~ and ~v~ denoting that ~u~ has an undirected edge to ~v~. You are guaranteed these edges will form a connected graph.

Output Format

Output a single integer, the longest distance between two trees of different colour.

Constraints

• ~2 \leq n \leq 10^5~
• ~0 \leq u, v < n~
• You are guaranteed there are no repeated edges.
• You are guaranteed the edges will form a connected graph.
• You are guaranteed at least two nodes will have different colours.

Sample Cases

Input 1

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

Output 1

4

Here nodes ~3~ and ~5~ have different seasons - season ~2~ and season ~1~ respectively - and are distance ~4~ apart. This is the longest distance between any two nodes of different seasons.

Input 2

10
3 4 4 4 4 1 1 2 3 4
2 3
2 8
3 5
5 4
3 6
6 0
3 1
6 7
5 9

Output 2

4