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.
// In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 3e5 + 5, mod = 1e9 + 7;// inf = 1e18;
ll n, a[maxn], ps[maxn] ,st[maxn], ft[maxn], tme, ans;
vector <pll> v[maxn];
vector <ll> adj[maxn];
void compress(){
	vector <ll> vec;
	for(ll i = 1; i <= n; i ++)vec.pb(a[i]);
	Sort(vec);
	vec.resize(unique(all(vec)) - vec.begin());
	for(ll i = 1; i <= n; i ++)a[i] = (lower_bound(all(vec), a[i]) - vec.begin()); 
}
void dfs(ll u, ll par){
	st[u] = tme ++;
	ll i = v[a[u]].size();
	v[a[u]].pb({st[u], ft[u]});
	for(ll j : adj[u]){
		if(j == par)continue;
		dfs(j, u);
	}
	ft[u] = tme;
	v[a[u]][i].S = ft[u];
}
ll get(ll u, ll c){
	if(v[c].size() == 0)return 0;
	if(v[c].back().F < st[u])return 0;
	pll p = {st[u], ft[u]};
	ll l = lower_bound(all(v[c]), p) - v[c].begin();
	if(v[c][l].S > ft[u])return 0;
	ll sz = v[c].size();
	if((v[c].back().S <= ft[u]) && (st[u] <= v[c].back().F))return sz - l;
	ll r = sz - 1ll, cur = l;
	while(l != r - 1ll){
		ll mid = (l + r) / 2ll;
		if(v[c][mid].S > ft[u])r = mid;
		else l = mid;
	}
	return l - cur + 1ll;
}
void dfs2(ll u, ll par){
	ll num = get(u, a[u]);
	if(num != v[a[u]].size())ps[u] ++;
	for(ll j : adj[u]){
		if(j == par)continue;
		if(get(j, a[u])){
			ps[1] ++;
			ps[j] --;
		}
		dfs2(j, u);
	}
}
void dfs3(ll u, ll par){
	if(ps[u] == 0)ans ++;
	for(ll j : adj[u]){
		if(j == par)continue;
		ps[j] += ps[u];
		dfs3(j, u);
	}
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for(ll i = 1; i <= n; i ++)cin >> a[i];
	compress();
	for(ll i = 1; i < n; i ++){
		ll u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1, 0);
	dfs2(1, 0);
	dfs3(1, 0);
	cout << ans << endl;
}
