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>
#define ll long long
using namespace std;
const int N = 2e5+10;
int in[N], out[N], a[N], cnt[N], id[N], arr[N];
map<int,int> f;
bool isGood[N], sub[N];
int n;
vector<int> edges[N], ok[N];
struct node {
	vector<int> v;
	void merge(vector<int> &a, vector<int> &b) {
		int i = 0, j = 0;
		v.reserve((int)a.size() + (int)b.size());
		while(i < (int)a.size() || j < (int)b.size()) {
			if(i < (int)a.size() && (j == (int)b.size() || a[i] < b[j])) {
				v.push_back(a[i++]);
			} else {
				v.push_back(b[j++]);
			}
		}
	}
	int search(int x) {
		int l = 0, r = (int)v.size() - 1, ind = -1;
		while(r >= l) {
			int m = l + r >> 1;
			if(v[m] <= x) {
				l = m + 1;
				ind = m;
			} else {
				r = m - 1;
			}
		}
		return ind+1;
	}
} tree[4 * N];
void build(int l, int r, int p) {
	int m = l + r >> 1;
	if(l == r) {
		tree[p].v.push_back(a[arr[l]]);
		return;
	}
	build(l, m, p << 1);
	build(m + 1, r, p << 1 | 1);
	tree[p].merge(tree[p << 1].v, tree[p << 1 | 1].v);
}
int query(int l, int r, int L, int R, int x, int p) {
	if(L > r || l > R) return 0;
	if(L <= l && R >= r) {
		return tree[p].search(x) - tree[p].search(x - 1);
	}
	int m = l + r >> 1;
	return query(l, m, L, R, x, p << 1) + query(m + 1, r, L, R, x, p << 1 | 1);
}
void dfs(int x, int p) {
	static int timer = 0;
	in[x] = ++timer;
	for(int to : edges[x]) {
		if(to != p) {
			dfs(to, x);
		}
	}
	out[x] = timer;
}
void rec(int x, int p) {
	if(x == 1) {
		isGood[x] = sub[x];
	} else if(!sub[x]) {
		isGood[x] = 0;
	} else if(!isGood[p]) {
		if(cnt[p] > 1) {
			isGood[x] = 0;
		} else {
			if(ok[p][id[x]] == 0) {
				if(f[a[x]] == 1) {
					isGood[x] = 1;
				} else {
					isGood[x] = 0; 
				}
			} else {
				isGood[x] = 0; 
			}
		}
	} else {
		if(f[a[x]] == 1) {
			isGood[x] = 1;
		} else {
			isGood[x] = 0; 
		}
	}
	if(x > 1) {
		bool must_increase = 0;
		if(f[a[x]] > query(1, n, in[x], out[x], a[x], 1)) {
			must_increase |= 1;
		}
		if(cnt[p] > 1) {
			must_increase |= 1;
		}
		if(cnt[p] == 1 && ok[p][id[x]] == 1) {
			must_increase |= 1;
		}
		if(must_increase) {
			++cnt[x];
		}
	}
	for(int to : edges[x]) {
		if(to != p) {
			rec(to, x);
		}
	}
}
void dfs_pull(int x, int p) {
	sub[x] = 1;
	for(int i = 0; i < edges[x].size(); ++i) {
		int to = edges[x][i];
		if(to != p) {
			dfs_pull(to, x);
			if(sub[to] == 0 || query(1, n, in[to], out[to], a[x], 1) > 0) {
				ok[x][i] = 0;
				++cnt[x];
				sub[x] = 0;
			}
			id[to] = i;
		} 
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		++f[a[i]];
	}
	for(int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
		ok[u].push_back(1);
		ok[v].push_back(1);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; ++i) {
		arr[in[i]] = i;
	}
	build(1, n, 1);
	dfs_pull(1, 0);
	rec(1, 0);
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		ans += isGood[i];
	}
	cout << ans << '\n';
}
