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<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int N=501000;
long long read(void)
{
	char ch=getchar();long long sum=0;bool f=0;
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-'){f=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	if(f)sum=-sum;return sum;
}
int n,tim,Len,All,tot;
int col[N],mp[N];
int dfn[N],siz[N],fa[N][21],dep[N];
int Add[N],Ans;
vector<int>G[N];
bool cmp(int aa,int bb){return dfn[aa]<dfn[bb];}
struct E{int num,next;}hd[N],edge[N*3];
void addedge(int x,int y){edge[++Len]=(E){y,hd[x].next};hd[x].next=Len;return;}
void AddE(int x,int y){addedge(x,y);addedge(y,x);return;}

void DFS(int u,int f)
{
	dfn[u]=++tim;dep[u]=dep[f]+1;siz[u]=1;
	fa[u][0]=f;
	for(int i=1;(1<<i)<=dep[u];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int p=hd[u].next,v;p;p=edge[p].next)
	{
		v=edge[p].num;if(v==f)continue;
		DFS(v,u);siz[u]+=siz[v];
	}return;
}
void DFS2(int u,int f)
{
	Add[u]+=Add[f];if(Add[u]==0)++Ans;
	for(int p=hd[u].next,v;p;p=edge[p].next)
	{
		v=edge[p].num;if(v==f)continue;
		DFS2(v,u);
	}return;
}
int LCA(int x,int y)
{
	if(dep[y]>dep[x])swap(x,y);
	for(int i=20;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void Modify(int x,int y)
{
	int t=LCA(x,y);
	if(t!=x&&t!=y){Add[x]++;Add[y]++;}
	else {
		if(t==y)swap(x,y);
		Add[y]++;Add[1]++;
		for(int p=hd[x].next,v;p;p=edge[p].next){
			v=edge[p].num;if(v==fa[x][0])continue;
			if(dfn[y]>=dfn[v]&&dfn[y]<=dfn[v]+siz[v]-1)Add[v]--;
		}
	}return;
}
void update(int now)
{
	int L=G[now].size();if(L<2)return;
	sort(G[now].begin(),G[now].end(),cmp);
	for(int i=0;i<L-1;i++){
		Modify(G[now][i],G[now][i+1]);
	}Modify(G[now][0],G[now][L-1]);
	return;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)col[i]=read(),mp[++tot]=col[i];
	sort(mp+1,mp+tot+1);tot=unique(mp+1,mp+tot+1)-mp-1;
	for(int i=1;i<=n;i++)col[i]=lower_bound(mp+1,mp+tot+1,col[i])-mp,G[col[i]].push_back(i);
	for(int i=1;i<=n-1;i++)AddE(read(),read());
	DFS(1,0);
	for(int i=1;i<=tot;i++)update(i);
	DFS2(1,0);
	cout<<Ans;return 0;
}