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.
// author: xay5421
// created: Fri Jan  8 22:33:36 2021
#include<bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=200005,K=20;
int n,tt,a[N],id[N],ind,dep[N],tin[N],tou[N],cf[N],fa[N][K];
int pp,lnk[N],nxt[N*2],to[N*2];
void ae(int k1,int k2){to[++pp]=k2,nxt[pp]=lnk[k1],lnk[k1]=pp;}
void dfs(int k1,int k2){
	tin[k1]=++ind,fa[k1][0]=k2,dep[k1]=dep[k2]+1;
	rep(i,1,K-1)fa[k1][i]=fa[fa[k1][i-1]][i-1];
	for(int i=lnk[k1];i;i=nxt[i])if(to[i]!=k2)dfs(to[i],k1);
	tou[k1]=ind;
}
int jump(int k1,int k2){
	for(int i=K-1;i>=0;--i)if(k2>>i&1)k1=fa[k1][i];
	return k1;
}
void sol(vector<int>v){
	if(SZ(v)==1)return;
	sort(v.begin(),v.end(),[&](int k1,int k2){return tin[k1]<tin[k2];});
	++tt;
	if(tin[v.back()]<=tou[v[0]]){
		rep(i,1,SZ(v)-2){
			if(tin[v[i+1]]<=tou[v[i]]){
				puts("0");
				exit(0);
			}
		}
		vector<int>son;
		rep(i,1,SZ(v)-1){
			int k1=v[i];
			k1=jump(k1,dep[k1]-dep[v[0]]-1);
			son.push_back(k1);
		}
		sort(son.begin(),son.end());
		son.erase(unique(son.begin(),son.end()),son.end());
		if(SZ(son)>1){
			puts("0");
			exit(0);
		}
		for(const auto&x:son){
			++cf[tin[x]],--cf[tou[x]+1];
		}
		rep(i,1,SZ(v)-1)--cf[tin[v[i]]],++cf[tou[v[i]]+1];
	}else{
		rep(i,0,SZ(v)-2){
			if(tin[v[i+1]]<=tou[v[i]]){
				puts("0");
				exit(0);
			}
		}
		++cf[1],--cf[n+1];
		rep(i,0,SZ(v)-1)--cf[tin[v[i]]],++cf[tou[v[i]]+1];
	}
}
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	scanf("%d",&n);
	rep(i,1,n)scanf("%d",&a[i]),id[i]=i;
	rep(i,1,n-1){
		int k1,k2;
		scanf("%d%d",&k1,&k2);
		ae(k1,k2),ae(k2,k1);
	}
	dfs(1,0);
	sort(id+1,id+1+n,[&](int k1,int k2){return a[k1]<a[k2];});
	for(int i=1,j;i<=n;i=j){
		j=i+1;
		while(j<=n&&a[id[i]]==a[id[j]])++j;
		vector<int>v;
		rep(k,i,j-1)v.push_back(id[k]);
		sol(v);
	}
	int ans=0;
	rep(i,1,n)cf[i]+=cf[i-1],ans+=cf[i]==tt;
	printf("%d\n",ans);
	return 0;
}
