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 <algorithm>
#include <vector>
using namespace std;

const int maxn = 2e5 + 5;

vector<int> g[maxn],v;
int dfn[maxn],siz[maxn],vx[maxn];
int num[maxn],tot[maxn],s[maxn];
int cnt = 0;
int n;

int get_id(int x)
{
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}

void update(int l,int r,int v)
{
	s[l] += v;
	s[r+1] -= v;
}

void dfs(int x,int fa)
{
	int id = get_id(vx[x]);
	dfn[x] = ++cnt;
	siz[x] = 1;
	int tmpx = num[id];
	num[id] ++;
	int flag = 0;
	for (int i = 0; i < g[x].size(); i++)
	{
		int t = g[x][i];
		if( t == fa ) continue;
		int pre = num[id];
		dfs(t,x);
		if( num[id] > pre ) 
		{
			update(1,n,-1);
			update(dfn[t],dfn[t]+siz[t]-1,1);
			flag = 1;
		}
		siz[x] += siz[t];
	}
	if( num[id]-tmpx < tot[id] ) update(dfn[x],dfn[x]+siz[x]-1,-1);
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> vx[i];
		v.push_back(vx[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for (int i = 1; i <= n; i++)
	{
		tot[get_id(vx[i])] ++;
	}
	//build(1,1,n);
	for (int i = 1; i < n; i++)
	{
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	//dfs(1,0);
	dfs(1,0);
	int tot = 0,ans = 0; 
	for (int i = 1; i <= n; i++)
	{
		tot += s[i];
		if( tot >= 0 ) ans ++;
	}
	cout << ans << '\n';
	return 0;
}