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 ends endss
#define starts startss
#define f first
#define s second
using namespace std;
const int N=2e5+5;
int timer,tmin[N],tmout[N],tree[2][4*N],n,a[N],u,v,ind[N],cnt[N],raod[N],ans,k,cur,i;
pair<int,int>b[N];
vector<pair<int,int> > M[N];
vector<int>V[N],ends[N],starts[N];
set<int>s;
set<pair<int,int> > S;
void dfs(int u,int p){
	timer++;
	tmin[u]=timer;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]!=p) dfs(V[u][i],u);
	}
	tmout[u]=timer;
}
void update(int u,int ind,int l,int r,int val,int t){
	if(l>ind || r<ind) return;
	if(l==r){
		if(t==1)tree[1][u]=val;
		else tree[0][u]+=val;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val,t);
	update(2*u+1,ind,mid+1,r,val,t);
	tree[1][u]=max(tree[1][2*u],tree[1][2*u+1]);
	tree[0][u]=tree[0][2*u]+tree[0][2*u+1];
}
int getans(int u,int start,int end,int l,int r,int t){
	if(l>end || r<start) return 0;
	if(start<=l && r<=end){
		return tree[t][u];
	}
	int mid=(l+r)/2;
	if(t==1)
	 return max(getans(2*u,start,end,l,mid,t),
	getans(2*u+1,start,end,mid+1,r,t));
	else return getans(2*u,start,end,l,mid,t)+getans(2*u+1,start,end,mid+1,r,t);
}
void dfs2(int u,int p){
	if(cnt[tmin[u]]!=raod[ind[u]]) return;
	if(getans(1,tmin[u],tmout[u],1,n,1)<tmin[u]) ans++; 
	int cc=0,c=0;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p) continue;
		if(getans(1,tmin[V[u][i]],tmout[V[u][i]],1,n,1)>=tmin[u]){
			cc++; c=V[u][i];
		}
	}
	if(cc>1)return;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p) continue;
		if(!cc)dfs2(V[u][i],u);
		else if(c==V[u][i])dfs2(c,u);
	}
}
int main(){
	cin>>n;
	for(k=1;k<=n;k++){
		cin>>a[k];
		b[k]={a[k],k};
	}
	for(k=2;k<=n;k++){
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	dfs(1,0);
	sort(b+1,b+n+1);
	for(k=1;k<=n;k++){
		if(b[k].f!=b[k-1].f){
			cur++;
		}
		ind[b[k].s]=cur; raod[cur]++;
		M[cur].push_back({tmin[b[k].s],tmout[b[k].s]});
	} //cout<<"+";
	for(k=1;k<=cur;k++){
		sort(M[k].begin(),M[k].end());
		S.clear();
		s.clear();
		s.insert(0);
	//	cout<<k<<"__"<<endl;
		for(i=0;i<M[k].size();i++){
		S.insert({M[k][i].f,i});
		 starts[i].clear(); ends[i].clear(); }
		for(i=0;i<M[k].size();i++){
			int c=i;
			for(int i=0;i<starts[c].size();i++){
				s.insert(starts[c][i]);
			}
			
			for(int i=0;i<ends[c].size();i++){
				s.erase(ends[c][i]);
			}
			
			int st=M[k][i].f;
			int en=M[k][i].s;
			update(1,st,1,n,*--s.end(),1);
			//cout<<st<<" "<<(*--s.end())<<endl;
			if(S.upper_bound({st,n})!=S.end()){
				starts[(*S.upper_bound({st,n})).s].push_back(st);
				if(S.upper_bound({en,n})!=S.end()){
					ends[(*S.upper_bound({en,n})).s].push_back(st);
				//	cout<<st<<"_"<<(*S.upper_bound({en,n})).s<<endl;
				}
			}
		}
		for(i=0;i<M[k].size();i++){
			update(1,M[k][i].f,1,n,1,0);
		}
		for(i=0;i<M[k].size();i++){
			cnt[M[k][i].f]=getans(1,M[k][i].f,M[k][i].s,1,n,0);
		}
		for(i=0;i<M[k].size();i++){
			update(1,M[k][i].f,1,n,-1,0);
		}
	}
//	cout<<"+";
	dfs2(1,0);
	cout<<ans;
	
}