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>
//#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1<<18;
const int STALA=18;
int t[MAX*2];
int ans=0;
int sub[MAX];
int c[MAX];
int cnt[MAX];
int pre[MAX];
int A[MAX][STALA];
int gle[MAX];
set<int>pom;
map<int,int>compress;
vi P[MAX];
void update(int u,int v,int ce){
   for (u+=MAX,v+=MAX+1;u<v;u>>=1,v>>=1){
      if (u&1)t[u++]+=ce;
      if (v&1)t[--v]+=ce;
   }
}
 
int query(int u){
   int sum=0;
   for (u+=MAX;u>0;u>>=1){
      sum+=t[u];
   }
   return sum;
}
int czas=0;
 
bool isuinv(int u,int v){
   return pre[v]<=pre[u] && pre[v]+sub[v]-1>=pre[u];
}
 
 
void dfs(int u,int fa){
   sub[u]++;
   A[u][0]=fa;
   pre[u]=++czas;
   for (auto it:P[u]){
      if (it==fa)continue;
      gle[it]=gle[u]+1;
      dfs(it,u);
      sub[u]+=sub[it];
   }
}
 
void add(int u){
   update(pre[u],pre[u]+sub[u]-1,1);
}
 
int czy(int u){
   return query(pre[u]);
}
 
vector<int>color[MAX];
int ile(int id,int l,int r){
   auto itl=lower_bound(color[id].begin(),color[id].end(),l)-color[id].begin();
   auto itr=--upper_bound(color[id].begin(),color[id].end(),r)-color[id].begin();
   return itr-itl+1;
}
 
int jump(int u,int ile){
   for (int i=STALA-1;i>=0;i--){
      if (ile-(1<<i)>=0)u=A[u][i],ile-=(1<<i);
   }
   return u;
}
int closest[MAX];
vi stos[MAX];
void dfs2(int u,int fa){
   if (!stos[c[u]].empty()){
      closest[u]=stos[c[u]].back();
   }
   stos[c[u]].pb(u);
   for (auto it:P[u]){
      if (it==fa)continue;
      dfs2(it,u);
   }
   stos[c[u]].pop_back();
}
int32_t main(){
  BOOST;
  int n;
  cin>>n;
  for (int i=1;i<=n;i++)cin>>c[i],pom.ins(c[i]);
  int licznik=1;
  for (auto it:pom)compress[it]=licznik++;
  for (int i=1;i<=n;i++)c[i]=compress[c[i]],cnt[c[i]]++;
  for (int i=1;i<=n-1;i++){
    int a,b;
    cin>>a>>b;
    P[a].pb(b);
    P[b].pb(a);
  }
  dfs(1,1);
  for (int i=1;i<STALA;i++)for (int j=1;j<=n;j++){
    A[j][i]=A[A[j][i-1]][i-1];
  }
  for (int i=1;i<=n;i++)color[c[i]].pb(pre[i]);
  for (int i=1;i<=n;i++)sort(color[i].begin(),color[i].end());
  for (int i=1;i<=n;i++){
    int zmienna=ile(c[i],pre[i],pre[i]+sub[i]-1);
    if (zmienna!=cnt[c[i]]){
      add(i);
    }
  }
  
  dfs2(1,-1);
  
  for (int i=1;i<=n;i++){
    if (!closest[i])continue;
    int x=jump(i,gle[i]-gle[closest[i]]-1);
   // cout<<"TERAZ "<<x<<" "<<i<<"\n";
    add(i);
    update(1,pre[x]-1,1);
    update(pre[x]+sub[x],n,1);
  }
  
  for (int i=1;i<=n;i++){
    if (!czy(i))ans++;
  }
  cout<<ans;
  return 0; 
}
