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;

using ll = long long;
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define POPCOUNT(x) __builtin_popcount(x)
template <typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template <typename T> void chmax(T &a, const T &b) { a = max(a, b); }

const ll INF = 1LL << 60;

struct FastIO {
    FastIO() {
        cin.tie(0);
        ios::sync_with_stdio(0);
    }
} fastiofastio;

// BEGIN CUT
struct segTreeRangeFreq {
    int n;
    vector<vector<ll>> dat;
    // 初期化 O(NlogN)
    segTreeRangeFreq() {}
    segTreeRangeFreq(vector<vector<ll>> v) {
        n = 1;
        while (n < (ll)v.size())
            n *= 2;
        dat.resize(2 * n - 1);
        REP(i, v.size()) dat[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; --i) {
            dat[i].resize(dat[i * 2 + 1].size() + dat[i * 2 + 2].size());
            merge(ALL(dat[i * 2 + 1]), ALL(dat[i * 2 + 2]), dat[i].begin());
        }
    }
    // [a, b) のx以下の個数を返す O(log^2N)
    int query(int a, int b, ll x, int k, int l, int r) {
        if (b <= l || r <= a)
            return 0;
        if (a <= l && r <= b)
            return upper_bound(ALL(dat[k]), x) - dat[k].begin();
        int vl = query(a, b, x, k * 2 + 1, l, (l + r) / 2);
        int vr = query(a, b, x, k * 2 + 2, (l + r) / 2, r);
        return vl + vr;
    }
    int query(int a, int b, ll x) { return query(a, b, x, 0, 0, n); }
};

// 2次元平面上の点集合 矩形中に何個点があるかのクエリに答えることが可能
// (x[i], y[i]) をxでソートしてyをセグ木に乗せるとrangefreqになる
// wavelet matrixじゃなくてセグ木でO(log^2N)でok
// END CUT

int L[200000], R[200000];
int a[200000];
int cnt[200000];
int add[200000];
int total;
int K;
vector<int> G[200000];
vector<vector<ll>> tour;
segTreeRangeFreq seg;

void dfs(int v, int par) {
    L[v] = tour.size();
    cnt[a[v]]++;
    tour.push_back({a[v]});
    for (int to : G[v]) {
        if (to == par)
            continue;
        dfs(to, v);
    }
    R[v] = tour.size();
}

void dfs2(int v, int par) {
    int sum = 1;
    for (int to : G[v]) {
        if (to == par)
            continue;
        dfs2(to, v);
        int ret =
            seg.query(L[to], R[to], a[v]) - seg.query(L[to], R[to], a[v] - 1);
        if (ret > 0) {
            add[to]++;
            K++;
            sum += ret;
        }
    }
    if (cnt[a[v]] > sum) {
        total++;
        add[v]--;
        K++;
    }
}

void dfs3(int v, int par) {
    for (int to : G[v]) {
        if (to == par)
            continue;
        add[to] += add[v];
        dfs3(to, v);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vec.push_back(a[i]);
    }
    sort(ALL(vec));
    vec.erase(unique(ALL(vec)), vec.end());
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(ALL(vec), a[i]) - vec.begin();
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(0, -1);
    seg = segTreeRangeFreq(tour);
    dfs2(0, -1);
    dfs3(0, -1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (total + add[i] == K)
            ans++;
    }
    cout << ans << endl;
}