You are given a tree with n vertices. Each vertex i has a value ai associated with it.
Let us root the tree at some vertex v. The vertex v is called a distinctive root if the following holds: in all paths that start at v and end at some other node, all the values encountered are distinct. Two different paths may have values in common but a single path must have all distinct values.
Find the number of distinctive roots in the tree.
Input
The first line of the input contains a single integer n (1≤n≤2⋅105) — the number of vertices in the tree.
The next line contains n space-separated integers a1,a2,…,an (1≤ai≤109).
The following n−1 lines each contain two space-separated integers u and v (1≤u, v≤n), denoting an edge from u to v.
It is guaranteed that the edges form a tree.
Output
Print a single integer — the number of distinctive roots in the tree.
Examples
input
5
2 5 1 1 4
1 2
1 3
2 4
2 5
output
3
input
5
2 1 1 1 4
1 2
1 3
2 4
2 5
output
0
Note
In the first example, 1, 2 and 5 are distinctive roots.
