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.
#include<bits/stdc++.h>
#define lowbit( x ) (x&(-x))
#define mp( x , y ) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair < int , int > P;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int n, a[N], c[N], cnt[N], num[N], in[N], out[N], tot;
int b[N], m; // 离散化
vector<int> G[N];
void dfs(int u, int fa)
{
    in[u] = ++ tot;
    int pre_num = num[a[u]];
    ++ num[a[u]];
    for(auto &v:G[u]) {
        if(v == fa) continue;
        int pre = num[a[u]];
        dfs(v, u);
        if(num[a[u]] != pre) {
            ++ c[1];
            -- c[in[v]];
            ++ c[out[v] + 1];
        }
    }
    out[u] = tot;
    if(pre_num || num[a[u]] != cnt[a[u]]) {
        ++ c[in[u]];
        -- c[out[u] + 1];
    }
}

int main () {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    int u, v;
    for(int i = 1; i < n; ++ i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i <= n; ++ i) {
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
        ++ cnt[a[i]];
    }
    dfs(1, - 1);
    int ans = 0;
    for(int i = 1; i <= n; ++ i) {
        c[i] += c[i - 1];
        if(!c[i]) {
            ++ ans;
        }
    }
    printf("%d\n", ans);
	return 0;
}