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 <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

#include <cmath>
#include <queue>
#include <stack>

#include <unordered_set>
#include <unordered_map>
#include <array>

using namespace std;

#define LL long long

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x) {
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writeln(int x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}

inline LL readll() {
    LL x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void writell(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writellln(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}

const int hashMod = 999983;

template<class TYPENAME>
class HashNode {
public:
    TYPENAME val;
    int key, next;
    HashNode(TYPENAME _val, int _key, int _next): val(_val), key(_key), next(_next) {}
    bool isNull() {
        return key == -1;
    }
};

template<class TYPENAME>
class Hash {
public:
    vector<HashNode<TYPENAME> > nodes;
    vector<int> d;
    int nodeN;
    Hash() {
        nodeN = 0; 
        d = vector<int>(hashMod, -1);
    }
    void push(int key, TYPENAME val) {
        nodes.push_back(HashNode<TYPENAME>(val, key, d[key]));
        d[key] = nodeN++;
    }
    HashNode<TYPENAME> find(int key, TYPENAME val) {
        for (int p = d[key]; p != -1; p = nodes[p].next) {
            if (nodes[p].val == val) {
                return nodes[p];
            }
        }
        return HashNode<TYPENAME>(val, -1, -1);
    }
};

class Nums {
	public:
	int idx, x;
	Nums(int _idx, int _x): x(_x), idx(_idx) {}
};

bool cmp(const Nums &a, const Nums &b) {
	return a.x < b.x;
}

vector<int> discretize(vector<int> &x, int &maxCur) {
	// cout << endl;
	vector<Nums> a;
	a.clear();
	for (int i = 0; i < x.size(); ++i) {
		a.push_back(Nums(i, x[i]));
	}
	sort(a.begin(), a.end(), cmp);
	int cur = 0;
	vector<int> res(a.size());
	for (int i = 0; i < a.size(); ++i) {
		// cout << a[i].idx << ' ' << a[i].x << endl;
		if (i != 0 && a[i].x != a[i - 1].x) {
			++cur;
		}
		res[a[i].idx] = cur;
	}
	maxCur = cur;
	return res;
}

class Edge {
public:
    int t;
    bool isDis;
    Edge(int _t): t(_t) {
        isDis = false;
    }
};
int n;
vector<vector<Edge> > e;
vector<int> sz;
vector<int> a;
vector<int> p;

vector<bool> vis;
vector<vector<int> *> ch;
vector<bool> iscd;
vector<bool> istd;
vector<int> ct, cti;

void dfs1(int u) {
    sz[u] = 1;
    vis[u] = true;
    for (Edge v: e[u]) {
        if (v.t != p[u]) {
            p[v.t] = u;
            dfs1(v.t);
            sz[u] += sz[v.t];
        }
    }
}

void dfs2(int u, bool keep) {
    // standard DSU-on-tree dfs, see https://codeforces.com/blog/entry/44351
    int maxSz = -1, maxIdx = -1, maxEIdx = -1;

    for (int i = 0; i < e[u].size(); ++i) {
        Edge v = e[u][i]; 
        if (v.t == p[u]) {
            continue;
        }
        if (sz[v.t] > maxSz) {
            maxSz = sz[v.t]; maxIdx = v.t; maxEIdx = i;
        }
    }

    for (Edge v: e[u]) {
        if (v.t != p[u] && v.t != maxIdx) {
            dfs2(v.t, false);
        }
    }

    if (maxIdx != -1) {
        dfs2(maxIdx, true);
        ch[u] = ch[maxIdx];
    } else {
        ch[u] = new vector<int>;
    }

    // before this, ch contains all the a[i]'s of the weighted child
    // and ct[w] is the number of a[u] == w appeared in the weighted child
    ch[u]->push_back(a[u]); ct[a[u]] += 1;

    // iscd[u] means u is a distinctive root of its subtree
    // it is true iff: 1. all its children are distinctive roots of its subtree
    // 2. a[u] does not appear in its subtree
    // we use flag to record this

    bool flag = true;
    if (maxIdx != -1) {
        if (!iscd[maxIdx]) {
            flag = false;
        }
    }

    // (u, v).isDis: whether u is a distinctive root, when we only consider the subtree v and u
    // it is true if iscd[v] == true, and u does not appear in subtree v

    if (ct[a[u]] == 1 && maxIdx != -1 && iscd[maxIdx]) {
        e[u][maxEIdx].isDis = true;
    }

    for (int i = 0; i < e[u].size(); ++i) {
        Edge v = e[u][i];
        if (v.t == p[u] || v.t == maxIdx) {
            continue; // only visit non-weighted children here
        }
        int nct = 0; // the number of nodes with a[x] == a[u] in this subtree
        for (int i = 0; i < ch[v.t]->size(); ++i) {
            int w = (*ch[v.t])[i];
            ch[u]->push_back(w); ++ct[w]; // standard DSU-on-tree operation
            if (w == a[u]) {
                ++nct;
            }
        }
        if (!iscd[v.t]) {
            flag = false;
        }
        if (nct == 0 && iscd[v.t]) {
            e[u][i].isDis = true;
            // if no a[u] in this subtree and iscd[v.t], then u is distinctive root for this subtree
        }
    }

    cti[u] = ct[a[u]];
    // record the number of a[u] appeared in its own subtree, a common DSU-on-tree query

    if (flag && ct[a[u]] == 1) {
        iscd[u] = true; // decide iscd[u] by all the iscd[v] of its children and whether a[u] appeared more than once
    }

    if (!keep) { // DSU-on-tree backward
        for (int v: (*ch[u])) {
            --ct[v];
        }
    }
}

void dfs3(int u) {
    // decide istd[u]
    // istd[u] is true iff: 1. istd[p[u]] == true
    // 2. p[u] is the distinctive root for any other subtrees under p[u]
    // 3. u does not appear in its parent part
    int tct = 0, cdt = 0;
    // tct: total number of subtrees
    // cdt: total number of subtrees where u is distinctive root
    for (Edge v: e[u]) {
        if (v.t != p[u]) {
            ++tct;
            if (v.isDis) {
                ++cdt;
            }
        }
    }
    for (Edge v: e[u]) {
        if (v.t == p[u]) {
            continue;
        }
        int curr = 0;
        if (v.isDis) {
            curr = 1;
        }
        // for (u, v): 
        // if u is the distinctive root for other subtrees, and its parent part
        // and all the appearance of a[v] is in subtree of v
        // then v is the distinctive root for its parent part
        if (istd[u] && (cdt - curr == tct - 1) && cti[v.t] == ct[a[v.t]]) {
            istd[v.t] = true;
        }
        dfs3(v.t);
    }
}
void solve() {
    int n = read();
    a = vector<int>(n);
    for (int i = 0; i < n; ++i) {
        a[i] = read();
    }
    int mc = 0;
    a = discretize(a, mc);
    e = vector<vector<Edge> >(n);
    for (int i = 0; i < n - 1; ++i) {
        int u = read() - 1, v = read() - 1;
        e[u].push_back(Edge(v)); e[v].push_back(Edge(u));
    }
    sz = vector<int>(n, 0);
    vis = vector<bool>(n, false);
    p = vector<int>(n, -1);
    dfs1(0);
    ch = vector<vector<int> *>(n);

    iscd = vector<bool>(n, false);
    // iscd[u]: if in the current rooted tree, u is a distinctive root of its subtree
    cti = vector<int>(n, 0);
    ct = vector<int>(mc + 1, 0);
    dfs2(0, false);

    istd = vector<bool>(n, false);
    // istd[u]: if node u is a distinct root when only considering its parent part(without its children)
    for (int i = 0; i < ct.size(); ++i) {
        ct[i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        ++ct[a[i]];
    }
    istd[0] = true;
    dfs3(0);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        // if (iscd[i] && istd[i] && ct[a[i]] == 1) {
        if (iscd[i] && istd[i]) {
            ++ans;
        }
    }
    cout << ans << endl;
}

int main() {
	// std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
	int t = 1;
	for (int i = 0; i < t; ++i) {
		solve();
	}
	return 0;
}