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 endl '\n'

int n;
int a[200055];

vector<int> g[200055];
map<int, vector<int>> c;

int dfn[200055], r[200055];
int t;

int dat[200055];
int par[200055];

int tot[200055];

void add(int id, int val, int *dat) {
    while (id < n) {
        dat[id] += val;
        id |= (id + 1);
    }
}
int get(int id, int *dat) {
    int res = 0;

    while (id >= 0) {
        res += dat[id];
        id = (id & (id + 1)) - 1;
    }

    return res;
}
void dfs(int v, int par = -1) {
    ::par[v] = par;
    dfn[v] = t++;
    for (auto u: g[v]) if (u != par) {
        dfs(u, v);
    }
    r[v] = t;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i + 1 < n; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(0);

    for (int i = 0; i < n; i++) {
        c[a[i]].push_back(i);
    }

    for (const auto &p: c) {
        auto vec = p.second;

        sort(vec.begin(), vec.end(), [&] (int v, int u) {
            return dfn[v] < dfn[u];
        });

        int m = (int)vec.size();

        for (auto v: vec) add(dfn[v], 1, dat);

        int root = 0;
        bool cool = false;

        for (auto v: vec) {
            int have = get(r[v] - 1, dat) - get(dfn[v] - 1, dat);

            if (have != 1 && have != m) {
                cout << 0 << endl;
                return 0;
            }

            if (have > 1) {
                cool = true;
                root = v;
            }
        }

        if (cool) {
            int choose = -1;

            for (auto u: g[root]) if (u != par[root]) {
                int have = get(r[u] - 1, dat) - get(dfn[u] - 1, dat);

                if (have == m - 1) {
                    if (choose != -1) {
                        cout << 0 << endl;
                        return 0;
                    }

                    choose = u;
                }
            }

            if (choose == -1) {
                cout << 0 << endl;
                return 0;
            }
            root = choose;
        }

        add(dfn[root], 1, tot);
        add(r[root], -1, tot);

        if (vec.size() > 1) {
            for (auto v: vec) if (dfn[v] >= dfn[root]) {
                add(dfn[v], -1, tot);
                add(r[v], 1, tot);
            }
        }

        for (auto v: vec) add(dfn[v], -1, dat);
    }

    int res = 0;

    for (int i = 0; i < n; i++) if (get(dfn[i], tot) == (int)c.size()) {
        res++;
    }

    cout << res;
}