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 N 200005
#define M 18
int read(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')f=(c=='-'?-f:f),c=getchar();
	while(c>='0'&&c<='9')w=w*10+c-'0',c=getchar();
	return w*f;
}
int n,a[N],dfn[N],rev[N],dl[N],dr[N],f[M][N],p[M],dep[N],cnt;
vector<int>e[N];
bool tag[N<<2];
set<int>s[N];
void update(int p,int x,int y,int l,int r){
	if(x<=l&&r<=y)return tag[p]=1,void();
	int mid=(l+r)>>1;
	if(x<=mid)update(p<<1,x,y,l,mid);
	if(y>mid)update(p<<1|1,x,y,mid+1,r);
}
int query(int p,int l,int r){
	if(tag[p])return 0;
	if(l==r)return 1;
	int mid=(l+r)>>1;
	return query(p<<1,l,mid)+query(p<<1|1,mid+1,r);
}
int Q(int p,int x,int l,int r){
	if(tag[p])return 0;
	if(l==r)return 1;
	int mid=(l+r)>>1;
	return x<=mid?Q(p<<1,x,l,mid):Q(p<<1|1,x,mid+1,r);
}
void dfs(int u,int ft){
	dfn[u]=dl[u]=++cnt;
	s[a[u]].insert(cnt);
	f[0][u]=ft,rev[cnt]=u,dep[u]=dep[ft]+1;
	for(auto v:e[u])
		if(v!=ft)dfs(v,u);
	dr[u]=cnt;
}
bool check(int x,int l,int r){
	auto it=s[x].lower_bound(l);
	return it!=s[x].end()&&*it<=r;
}
int find(int x,int l,int r){
	return rev[*s[x].lower_bound(l)];
}
void work(int x){
	bool fl=0;
	if(dl[x]>1)fl|=check(a[x],1,dl[x]-1);
	if(!fl&&dr[x]<n)fl|=check(a[x],dr[x]+1,n);
	if(fl)update(1,dl[x],dr[x],1,n);
	for(auto v:e[x]){
		if(v==f[0][x])continue;
		if(check(a[x],dl[v],dr[v])){
			int l=find(a[x],dl[v],dr[v]);
			for(int i=M-1;i>=0;i--)
				if(dep[l]-p[i]>dep[x])l=f[i][l];
			if(dl[l]>1)update(1,1,dl[l]-1,1,n);
			if(dr[l]<n)update(1,dr[l]+1,n,1,n);
		}
	}
}
map<int,int>mp;
signed main(){
	n=read();
	for(int i=1,tot=0;i<=n;i++){
		a[i]=read();
		if(mp[a[i]])a[i]=mp[a[i]];
		else a[i]=mp[a[i]]=++tot;
	}
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0),p[0]=1;
	for(int i=1;i<M;i++)
		p[i]=p[i-1]<<1;
	for(int i=1;i<M;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=f[i-1][f[i-1][j]];
	for(int i=1;i<=n;i++)//{
		work(i);
//		cout<<a[i]<<' ';
//		for(int j=1;j<=n;j++)
//			cout<<Q(1,j,1,n)<<' ';
//		cout<<endl;
//	}
//	for(int i=1;i<=n;i++)
//		cout<<Q(1,i,1,n)<<endl;
	printf("%d\n",query(1,1,n));
	return 0;
}