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 fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define FOR(i, a, b) for (int i = a; i <= (b); i++)
#define ROF(i, a, b) for (int i = a; i >= (b); i--)
#define y1 awefakhlrv

using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long;
using pll = pair<ll, ll>; using vpll = vector<pll>;
using vll = vector<ll>; using vvll = vector<vll>;

const int N = 200005;
int in[N], out[N], da[N], a[N], tot;
vi e[N];
map <int, int> cnt;

void dfs1(int u, int p) {
    in[u] = ++tot;
    for (int v : e[u]) {
        if (v == p) continue;
        dfs1(v, u);
    }
    out[u] = tot;
}

map <int, int> lst;
int nx[N];

map <int, int> dfs2(int u, int p) {
    if (lst[a[u]]) {
        da[in[1]]++, da[out[1] + 1]--;
        int son = nx[lst[a[u]]];
        da[in[son]]--, da[out[son] + 1]++;
        da[in[u]]++, da[out[u] + 1]--;
    }
    int ori = lst[a[u]];
    lst[a[u]] = u;
    map <int, int> rt;
    for (int v : e[u]) {
        if (v == p) continue;
        nx[u] = v;
        map <int, int> tt = dfs2(v, u);
        if (tt.size() > rt.size()) swap(tt, rt);
        for (pii i : tt)
            rt[i.fi] += i.se;
    }
    lst[a[u]] = ori;
    rt[a[u]]++;
    if (rt[a[u]] != cnt[a[u]]) {
        da[in[u]]++, da[out[u] + 1]--;
    }
    return rt;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    FOR(i, 1, n) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    FOR(i, 2, n) {
        int u, v; cin >> u >> v;
        e[u].pb(v);
        e[v].pb(u);
    }
    dfs1(1, -1);
    dfs2(1, -1);
    int ans = 0, tt = 0;
    FOR(i, 1, n) {
        tt += da[i];
        if (tt == 0) ans++;
        // cout << tt << ' ';
    }
    // cout << endl;
    cout << ans << endl;
}