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;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 2e5+7,M = 2 * N,LIM = 18;
int edge[M],succ[M],ver[N],idx;
int depth[N],fa[N][LIM + 3];
int a[N],cnt[N],dwcnt[N],sum[N];
int dfn[N],time_stamp,siz[N],n;
vector<int> val;
inline int link(int x)
{
	return lower_bound(val.begin(),val.end(),x) - val.begin();
}

void cover(int l,int r,int v)
{
	if(l > r)	return ;
	sum[l] += v;
	sum[r + 1] -= v;
}

void add(int u,int v)
{
	edge[idx] = v;
	succ[idx] = ver[u];
	ver[u] = idx++;
}

void dfs(int u,int fa)
{
	dfn[u] = ++time_stamp;	siz[u] = 1;
	int allu = dwcnt[a[u]];
	++dwcnt[a[u]];
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(v == fa)	continue;
		int other = dwcnt[a[u]];
		dfs(v,u);
		if(dwcnt[a[u]] > other)
		{
			cover(1,n,1);
			cover(dfn[v],dfn[v] + siz[v] - 1,-1);
		}
		siz[u] += siz[v];
	}
	allu = dwcnt[a[u]] - allu;
	if(allu < cnt[a[u]])	cover(dfn[u],dfn[u] + siz[u] - 1,1);
}

int main()
{
	memset(ver,-1,sizeof ver);
	scanf("%d",&n);
	
	forn(i,1,n)	scanf("%d",&a[i]),val.push_back(a[i]);
	sort(val.begin(),val.end());
	val.erase(unique(val.begin(),val.end()),val.end());
	forn(i,1,n)	a[i] = link(a[i]),++cnt[a[i]];
	
	forn(i,1,n - 1)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	
	dfs(1,-1);
	
	forn(i,1,n)	sum[i] += sum[i - 1];
	int res = 0;
	forn(i,1,n)	res += (sum[i] == 0);
	printf("%d",res);
	
    return 0;
}
