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 pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())

constexpr int maxn = 4e5+10, logn = 20;

struct BIT {
	int bit[maxn];
	void upd(int x, int v) {
		for(; x < maxn; x += x&-x)
			bit[x] += v;
	}
	int query(int x) {
		int ans = 0;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	void itv(int l, int r) {
		upd(l, 1); upd(r+1, -1);
	}
} bit;

int a[maxn], pai[maxn][logn], in[maxn], out[maxn], depth[maxn], qtd[maxn], t;
vector<int> grp[maxn], g[maxn];

void dfs(int u, int p) {
	pai[u][0] = p;
	in[u] = ++t;
	for(int v : g[u]) {
		if(v == p) continue;
		depth[v] = depth[u]+1;
		dfs(v, u);
	}
	out[u] = ++t;
}

int lca(int a, int b) {
	if(a == b) return a;
	if(depth[a] < depth[b])
		swap(a, b);
	for(int l = logn - 1; l >= 0; l--)
		if(depth[a] - (1 << l) >= depth[b])
			a = pai[a][l];
	if(a == b) return a;
	for(int l = logn - 1; l >= 0; l--)
		if(pai[a][l] != pai[b][l])
			a = pai[a][l], b = pai[b][l];
	return pai[a][0];
}

int main() {
	int n; scanf("%d", &n);

	map<int,int> mp;
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]), mp[a[i]];
	int aux = 0;
	for(auto& it : mp)
		it.second = ++aux;
	for(int i = 1; i <= n; i++)
		a[i] = mp[a[i]], grp[a[i]].pb(i);

	for(int i = 1; i < n; i++) {
		int u, v; scanf("%d %d", &u, &v);
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1, 0);

	for(int l = 1; l < logn; l++)
		for(int i = 1; i <= n; i++)
			pai[i][l] = pai[pai[i][l-1]][l-1];

	for(int j = 1; j <= aux; j++) {
		if(sz(grp[j]) <= 1) continue;
		sort(all(grp[j]), [](int x, int y){return in[x] < in[y];});

		vector<int> b = {grp[j][0]};
		for(int i = 1; i < sz(grp[j]); i++) {
			int x = grp[j][i], y = grp[j][i-1];
			int LCA = lca(x, y);
			b.pb(x);
			b.pb(LCA);
		}

		sort(all(b), [](int x, int y){return in[x] < in[y];});
		b.erase(unique(all(b)), b.end());

		int menor = depth[b[0]];

		for(int i = 1; i < sz(b); i++) {
			int LCA = lca(b[i], b[i-1]);
			menor = min(menor, depth[b[i]]);
			++qtd[LCA];
			++qtd[b[i]];
		}

		for(int i = 0; i < sz(b); i++) {
			if(a[b[i]] == j && qtd[b[i]] > 1) {
				puts("0"); return 0;
			}
			qtd[b[i]] = 0;
			if(a[b[i]] == j) {
				if(depth[b[i]] == menor) {
					int opa = -1, oto = i>0?b[0]:b[1];
					for(int v : g[b[i]]) {
						if(v == pai[b[i]][0]) continue;
						if(lca(oto, v) == v) {
							opa = v;
							break;
						}
					}
					bit.itv(1, in[opa]-1), bit.itv(out[opa]+1, 2*n);
				}
				else bit.itv(in[b[i]], out[b[i]]);
			}
		}

		b.clear();
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
		if(!bit.query(in[i])) ++ans;
	printf("%d\n", ans);
}