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 N = 2e5 + 3;

int n, ans;
int a[N], pref[N];
vector <int> g[N];
map <int, int> cnt;

void Merge(multiset <int> &a, multiset <int> &b) {
    if (a.size() < b.size()) {
        swap(a, b);
    }
    for (auto x : b) {
        a.insert(x);
    }
}

void dfs(int v, multiset <int>& mst, int pr) {
    vector <int> b;
    for (int to : g[v]) {
        if (to == pr) continue;
        multiset <int> new_mst;
        dfs(to, new_mst, v);
        if (new_mst.count(a[v])) {
            b.push_back(to);
        }
        Merge(mst, new_mst);
    }
    mst.insert(a[v]);
    if (cnt[a[v]] != mst.count(a[v])) {
        b.push_back(-1);
    }
    if (b.size() >= 2) {
        pref[1]++;
        return;
    }
    if (b.empty()) return;
    if (b[0] == -1) {
        pref[v]++;
    } else {
        pref[1]++;
        pref[b[0]]--;
    }
}

void dfs2(int v, int pr = -1) {
    if (!pref[v]) ans++;
    for (int to : g[v]) {
        if (to == pr) continue;
        pref[to] += pref[v];
        dfs2(to, v);
    }
}

int main()
{
	ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    multiset <int> mst;
    dfs(1, mst, -1);
    dfs2(1);
    cout << ans << endl;
}
