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 mxN = 1e6 + 5, mod = 1e9 + 7;

int n, a[mxN], cnt[mxN];

bool bad[mxN], bad_sub[mxN], sub[mxN];

vector <int> adj[mxN], ver[mxN];

multiset <int> st[mxN];

void dfs(int v, int par = -1, bool del = 0) {
	if (!ver[a[v]].empty()) { // delete all nodes in v's subtree
		int p = ver[a[v]].back();
		bad_sub[p] = 1;
		sub[v] = 1;
	}
	ver[a[v]].push_back(v);
	st[v].insert(a[v]);
	del |= sub[v];
	for (auto to : adj[v]) {
		if (to != par) {
			dfs(to, v, del);
			bad_sub[v] |= bad_sub[to];
			del |= bad_sub[v];
			if (st[v].size() < st[to].size()) 
				st[v].swap(st[to]);
			for (auto x : st[to])
				st[v].insert(x);
			st[to].clear();
		}
	}
	int c = st[v].count(a[v]) + ver[a[v]].size() - 1;
	if (c < cnt[a[v]]) // delete all nodes in v's subtree
		sub[v] = del = 1;
	bad[v] |= del;
	ver[a[v]].pop_back();
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];;
	{
		vector <int> vals;
		for (int i = 1; i <= n; ++i) vals.push_back(a[i]);
		sort(vals.begin(), vals.end());
		for (int i = 1; i <= n; ++i) a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
		for (int i = 1; i <= n; ++i) ++cnt[a[i]];
	}
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		adj[u].push_back(v); adj[v].push_back(u);
	}
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		reverse(adj[i].begin(), adj[i].end());
		bad_sub[i] = 0;
		st[i].clear(); 
	}
	dfs(1);
	int ans = 0;
	for (int i = 1; i <= n; ++i) ans += !bad[i];
	cout << ans;
	return 0;
}