Distinctive Roots in a Tree

You are given a tree with n vertices. Each vertex i has a value a_i 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⋅10^5) — the number of vertices in the tree.

The next line contains n space-separated integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

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.

inputFormat

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 2⋅10^5) — the number of vertices in the tree.

The next line contains n space-separated integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

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.

outputFormat

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.

样例

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

3

</p>