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;
#define pb emplace_back
#define sz(a) ((int)a.size())
typedef long long ll;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

vector<int> G[maxn];
int a[maxn], xi[maxn], dfn[maxn], siz[maxn], sum[maxn], tot[maxn], dt[maxn];
int n, tim, cntX;

void add(int l, int r, int v){

    dt[l] += v, dt[r + 1] -= v;
}

void dfs(int u, int f){

    siz[u] = 1, dfn[u] = ++tim;
    int tsum = sum[a[u]]; ++sum[a[u]];
    for(auto &v : G[u]){

        if(v == f) continue;
        int tmp = sum[a[u]];
        dfs(v, u);
        siz[u] += siz[v];
        if(sum[a[u]] > tmp){

            add(1, n, 1);
            add(dfn[v], dfn[v] + siz[v] - 1, -1);
        }
    }
    if(sum[a[u]] - tsum < tot[a[u]]){

        add(dfn[u], dfn[u] + siz[u] - 1, 1);
    }
}

int main(){

    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){

        cin >> a[i];
        xi[++cntX] = a[i];
    }
    sort(xi + 1, xi + 1 + cntX);
    cntX = unique(xi + 1, xi + 1 + cntX) - xi - 1;
    for(int i = 1; i <= n; ++i){

        a[i] = lower_bound(xi + 1, xi + 1 + cntX, a[i]) - xi;
        ++tot[a[i]];
    }
    for(int i = 1; i < n; ++i){

        int u, v; cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    dfs(1, 0);
    int ret = 0;
    for(int i = 1; i <= n; ++i){

        dt[i] += dt[i - 1];
        ret += dt[i] == 0;
        // cout << i << " ?? " << dt[i] << endl;
    }
    cout << ret << endl;
    return 0;
}