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;

int n,v[200010],hed[400010],cnt,b[200010],m;
int num,f[200010],xu[200010],ed[200010];
int tong[200010],ans,s[200010],ss[200010];
struct node
{
	int to,next;
}a[800010];
struct tree
{
	int l,r,sum;
}tr[4000010];
inline void add(int from,int to)
{
	a[++cnt].to=to;
	a[cnt].next=hed[from];
	hed[from]=cnt;
}
inline void dfs(int x)
{
	xu[x]=++num;
	int ji1=ss[v[x]];
	++ss[v[x]];
	for(int i=hed[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==f[x])
		continue;
		int ji2=ss[v[x]];
		f[y]=x;
		dfs(y);
		if(ss[v[x]]>ji2)//×ÓÊ÷ÄÚÓÐÕâ¸öÊý£¬ÄÇÃ´ÆäËû×ÓÊ÷¶¼²»ºÏ·¨
		{
			s[1]++;
			s[xu[y]]--;
			s[ed[y]+1]++;
		}
	}
	ed[x]=num;
	if(ss[v[x]]-ji1<tong[v[x]])//×ÓÊ÷ÍâÓÐÕâ¸öÊý£¬×ÓÊ÷ÄÚµÄ¶¼²»ºÏ·¨ 
	{
		s[xu[x]]++;
		s[ed[x]+1]--;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&v[i]);
		b[i]=v[i];	
	}
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	cnt=0;	
	for(int i=1;i<=n;++i)
	{
		v[i]=lower_bound(b+1,b+m+1,v[i])-b;
		tong[v[i]]++;
	}
	dfs(1);
	for(int i=1;i<=n;++i)
	{
		s[i]=s[i-1]+s[i];
		if(s[i]==0)
		++ans;
	}
	printf("%d\n",ans);
	return 0;
}