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<cstring>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
const int mod = 1e9 + 7 ;
vector<int> vec , g[maxn] ;
int a[maxn] ;
int sum[maxn] , sta[maxn] , ed[maxn] , cnt ;
int num[maxn] ;		//遍历过程每个数的出现次数
int mum[maxn] ;		//初始每个数的出现次数
void dfs(int x , int fa){
	sta[x] = ++cnt ;
	int now_v = num[a[x]] ;
	num[a[x]]++ ;
	for(int i = 0 ; i < g[x].size() ; i++){
		int v = g[x][i] ;
		if(v == fa)	continue ;
		int pre = num[a[x]] ;
		dfs(v , x) ;
		if(num[a[x]] > pre){		//第二种情况 
			sum[1]++ ;				//这个子树有a[x] ， 则x以及其他子树的点都非法 
			sum[sta[v]]-- ;
			sum[ed[v]+1]++ ;
		}
	}
	ed[x] = cnt ;
	if(num[a[x]] - now_v != mum[a[x]]){		//第一种情况 
		sum[sta[x]]++ ;						//连向父节点的子树有a[x]，那么x以及x对应其他子树非法
		sum[ed[x]+1]-- ;
	}
}

int main(){
	int n ;
	cin >> n ;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i] ;
		vec.push_back(a[i]) ;
	}
	sort(vec.begin() , vec.end()) ;
	vec.erase(unique(vec.begin() , vec.end()) , vec.end()) ;
	for(int i = 1 ; i <= n ; i++){
		a[i] = lower_bound(vec.begin() , vec.end() , a[i]) - vec.begin() ; 
		mum[a[i]]++ ;
	}
	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 , -1) ;
	int ans = 0 ;
	for(int i = 1 ; i <= n ; i++){
		sum[i] += sum[i-1] ;
		if(sum[i] == 0)
			ans++ ;
	}
	cout << ans << endl ;
	return 0 ;
}
