Problem Statement

A Kadomatsu sequence is a sequence $A_1, A_2, A_3$ of $3$ elements that satisfies both of the following 2 conditions.

• $A_1, A_2, A_3$ are all distinct
• Among the $3$ elements, $A_2$ is the largest or $A_2$ is the smallest

A tree in which vertex $i$ has the value $A_i$ is called a Kadomatsu tree if it satisfies the following.

• Let $v$ be a vertex of degree 2 or more, and let $u,w$ ($u \neq w$) be two vertices adjacent to $v$. Then for all such $u,v,w$, the sequence $A_u, A_v, A_w$ is a Kadomatsu sequence
  (Equivalently, for any three consecutive vertices $u,v,w$ taken from the tree, the sequence $A_u, A_v, A_w$ is a Kadomatsu sequence)

At the Kadomatsu Tree Fair, which is held irregularly, trees are scored and evaluated as follows.

1. If the tree is not a Kadomatsu tree, its score is 0 points.
2. If the tree is a Kadomatsu tree, its score is the number of Kadomatsu sequences contained in the tree.
   Let $v$ be a vertex of degree 2 or more, and let $u,w(u \neq w)$ be two vertices adjacent to $v$. When the sequence $A_u, A_v, A_w$ is a Kadomatsu sequence, the vertex set $\{u,v,w\}$ is counted as one Kadomatsu sequence. Here, $\{u,v,w\}$ and $\{w,v,u\}$ are regarded as identical and are not counted twice.

Kadomatsu-san owns one tree. It has $N$ vertices, and vertex $i$ has the value $A_i$.
Kadomatsu-san plans to enter one subtree of this tree in the Kadomatsu Tree Fair.
Find the maximum score Kadomatsu-san can obtain at the fair. Note that only one tree can be entered.

Input

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{n-1}$ $y_{n-1}$

The first line contains the number of vertices $N$ of the tree.
The second line contains the values $A_i$ of vertices $i$, separated by spaces.
The following $N-1$ lines, starting from the third line, give the edges. The $i$-th edge connects vertex $x_i$ and vertex $y_i$.

All inputs are integers and satisfy the following constraints.
$1 \leq N \leq 5 \times 10^4$
$1 \leq A_i \leq 10^3$
$1 \leq x_i,y_i \leq N$
$x_i \neq y_i$
It is guaranteed that the tree has no multiple edges or self-loops and is connected.

Output

Output the maximum score Kadomatsu-san can obtain.

Sample

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

4

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

2

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

0