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 <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

const int MAXN = 2e5 + 10;
int n, st[MAXN], fn[MAXN], a[MAXN], S, p[MAXN], pa[MAXN];
map<int, vector<int> > mp;
vector<int> Mat[MAXN];

void dfs(int v, int par) {
    pa[v] = par;
    st[v] = ++S;
    for (int u : Mat[v])
        if (u != par) {
            p[u] += p[v];
            dfs(u, v);
        }
    fn[v] = S;
}

bool check(int v, int u) {
    return st[u] <= st[v] && fn[v] <= fn[u];
}

bool cmp(int a, int b) {
    return st[a] < st[b];
}

void del(int a, int b) {
    for (int u : Mat[b])
        if (u != pa[b] && check(a, u))
            p[u]--;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], mp[a[i]].push_back(i);
    for (int i = 0; i < n - 1; i++) {
        int x, b;
        cin >> x >> b;
        Mat[x].push_back(b);
        Mat[b].push_back(x);
    }
    dfs(1, 1);
    for (auto q : mp) {
        vector<int> t = q.second, tmp;
        sort(t.begin(), t.end(), cmp);
        tmp.push_back(t[0]);
        int cur = 1;
        while (cur < t.size()) {
            if (tmp.empty()) {
                tmp.push_back(t[cur]);
                cur++;
                continue;
            }
            int x = t[cur], y = tmp.back();
            if (check(x, y)) {
                p[1]++;
                p[x]++;
                del(x, y);
                tmp.push_back(x);
                cur++;
            }
            else {
                p[x]++;
                p[y]++;
                tmp.pop_back();
            }
        }
    }
    dfs(1, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (p[i] == 0)
            ans++;
    cout << ans;
}