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>
using namespace std;
const int maxn = 2e5+10;
int a[maxn];
int b[maxn];
int cnt[maxn];
int dfn[maxn];
int c[maxn];
int nowsum[maxn];
vector<int> Edge[maxn];
int n;
int tot = 0;
int siz[maxn];

void cover(int l, int r, int k){
    if(l > r){
        return;
    }
    c[l] += k;
    c[r+1] -= k;
}

void dfs(int i, int fa){
    dfn[i] = ++tot;
    siz[i] = 1;
    int temp = nowsum[a[i]];
    ++nowsum[a[i]];
    for(auto v : Edge[i]){
        if(v == fa){
            continue;
        }
        int tmp = nowsum[a[i]];
        dfs(v, i);
        if(nowsum[a[i]] > tmp){
            cover(1, n, 1);
            cover(dfn[v], dfn[v]+siz[v]-1, -1);
        }
        siz[i] += siz[v];
    }
    if(nowsum[a[i]] - temp < cnt[a[i]]){
        cover(dfn[i], dfn[i]+siz[i]-1, 1);
    }
}

int main(){

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b+1, b+1+n);
    int m = unique(b+1, b+1+n) - b - 1;
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(b+1, b+1+n, a[i]) - b;
        cnt[a[i]]++;
    }
    for(int i = 1, u ,v; i <= n-1; i++){
        cin >> u >> v;
        Edge[u].push_back(v);
        Edge[v].push_back(u);
    }

    dfs(1, 0);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        c[i] += c[i-1];
        if(c[i] == 0){
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}