Migrated from Lutece 1559 B0n0 Path

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a country with $N$ cities, there are roads between some pairs of cities.

For every pair of cities, there is exactly one path between them, on which there are no cities passed more than once.

So it is obvious that there are $N-1$ roads and $\frac{N(N-1)}{2}$ paths.

The cities number from $1$ to $N$, and the $i^{th}$ city has one number $A_i$.

A path is Bono if and only if the numbers $A_i$ on the path are non-strictly increasing or decreasing.

i.e., if the numbers are $A_{b_1}, A_{b_2}, \dots, A_{b_m}$, $A_{b_i}\leq A_{b_{i+1}}\ , \forall 1\leq i\lt m$ or $A_{b_i}\geq A_{b_{i+1}}\ , \forall 1\leq i\lt m$ should be satisfied.

How many Bono paths in the country?

Input

The first line contains one integer $N$.

The second line contains $N$ integers, where the $i^{th}$ indicates $A_i$.

For the next $N-1$ lines, each line contains two integers $u, v$, meaning that there is a road between $u^{th}$ city and $v^{th}$ city.

$1\leq N\leq 10^5, 1\leq u, v\leq N, 1\leq A_i \leq 10^9$

Output

One integer indicating the number of bono paths in the country.

Samples

4
1 7 1 9
1 3
1 4
2 1

5

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

15

Note

For sample 1:

The format of the text on $i^{th}$ node is $(i:A_i)$.

There are 5 bono paths: $(1, 2), (1, 3), (1, 4), (2, 1, 3), (3, 1, 4)$, while path $(2, 1, 4)$ is not bono path.

For sample 2:

All path are bono paths.

Resources

The 15th UESTC Programming Contest Preliminary