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.
//BISMILLAHIR RAHMANIR RAHIM
#include<bits/stdc++.h>


//Solution Idea

//
using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair <pii , int> piii;
typedef pair<double, int > pdi;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef pair < ll , pll > plll;
typedef pair < pll , pll > pllll;

#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define endl '\n'
#define mx 100005
#define mx1 100005
#define mx2 200005
#define mx3 300005
#define WHITE 0
#define RED 1
#define BLACK 2

#define bp __builtin_popcountll
#define fraction() cout.unsetf(ios::floatfield); cout.precision(20); cout.setf(ios::fixed,ios::floatfield);
#define hi cout<<"Dhukse " << endl;
#define si(x) scanf("%d",&x)
#define sii(x,y) scanf("%d %d",&x,&y)
#define siii(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sll(x,y) scanf("%lld %lld",&x,&y)
#define slll(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)

const double PI = acos(-1);
const double eps = 1e-12;
const int inf = 2000000000;
const ll infLL = (ll)1e18;
ll MOD =  1000000007;
int MOD1 = 1000000007;
int MOD2 = 1000000009;

#define harmonic(n) 0.57721566490153286l(Eulers-Mascharoni constant)+log(n) ( 1/1 + 1/2 + .... + 1/n );

#define mem(a,b) memset(a, b, sizeof(a) )
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define sqr(a) ((a) * (a))
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;

inline bool checkBit(ll n, ll i) { return n&(1LL<<i); }
inline ll setBit(ll n, ll i) { return n|(1LL<<i);; }
inline ll resetBit(ll n, ll i) { return n&(~(1LL<<i)); }
#define LSBIT(X)                    ((X) & (-(X)))
#define CLEARLSBIT(X)               ((X) & ((X) - 1))

int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};
//int dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
//int dy[] = {0, +1, 0, -1, +1, -1, +1, -1};

inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
inline bool isLeapYear(ll year) { return (year%400==0) || (year%4==0 && year%100!=0); }
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1LL; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1LL; } return r; }
inline ll modDiv(ll a, ll b) { return modMul(a, modPow(b, MOD-2)); }

bool comp( const pair < ll , pll > &p1 , const pair < ll , pll > &p2 ){ return p1.F > p2.F ;}
bool comp1( const pll &p1 , const pll &p2 ){
          if( p1.F == p2.F ){
                 return p1.S > p2.S;
          }
          return p1.F < p2.F ;
}
ll converter( string a ){
    ll i , mul = 1LL , r , t ,ans = 0LL;if( a.length() == 0 )return 0;for( i = a.length() - 1 ; i >= 0 ; i-- ){
        t = a[i] - '0';r = t%10;ans += (mul*r);mul = mul*10;
    }
    return ans;
}
int msb(unsigned x) {
    union { double a; int b[2]; };
    a = x;
    return (b[1] >> 20) - 1023;
}

//
//debug
#ifndef ONLINE_JUDGE
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
            return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
            os << "{";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                    return os << "]";
}

template < typename T >
ostream &operator << ( ostream & os, const multiset< T > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                        return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << it -> first << " = " << it -> second ;
                                            }
                    return os << "]";
}

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)

void faltu () {
            cerr << endl;
}

template <typename T>
void faltu( T a[], int n ) {
            for(int i = 0; i < n; ++i) cerr << a[i] << ' ';
                cerr << endl;
}

template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) {
            cerr << arg << ' ';
                faltu(rest...);
}
#else
#define dbg(args...)
#endif  


const int MAX = 200005;

ll sum[MAX] , a[MAX] ,st[MAX] , en[MAX], par[MAX] , n , timer;
vector<int>adj[MAX];
map<int,vector<piii>>store;
void update(int x, int y , int val){
  if(val == 1) sum[x]++ , sum[y+1]--;
  else sum[x]-- , sum[y+1]++;
}
void dfs(int u , int p){
  st[u] = ++timer;
  en[u] = st[u];
  for(auto v: adj[u]) if(v != p) {
    par[v] = u;
    dfs(v,u);
    en[u] = max(en[u] , en[v]);
  }
}
int main() {
    optimize(); 
    fraction();
    
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin) ;
    freopen("output.txt","w",stdout);
     #endif
    cin >> n;
    for(int i = 1 ; i <= n; ++i) cin >> a[i];
    for(int i = 1 ; i < n; ++i) {
      int x, y; cin >> x >> y;
      adj[x].PB(y);
      adj[y].PB(x);
    }
    dfs(1,0);

    for(int i = 1 ; i <= n; ++i) {
      //dbg(i , st[i] , en[i]);
      store[a[i]].PB({{st[i] , en[i]} , i});
    }
    for(auto it : store){
      int x = it.F;
      sort(store[x].begin() , store[x].end());
      //dbg(store[x]);
    }

    //return 0;

    for(int i = 1 ; i <= n; ++i) {
      int cnt = 0 , sv , idx;
      int sz = store[a[i]].size() ;
      if(sz == 1) continue;

        for(int j = 0 ; j < adj[i].size() ; ++j) {
          int v = adj[i][j];
          if(v == par[i] ) continue;
          auto it1 = distance(store[a[i]].begin(), lower_bound(all(store[a[i]]) ,piii{{st[v],-1},-1}));
          //if(i == 1 && v == 3)dbg(it1,store[a[i]].size());
          if(it1 < sz && store[a[i]][it1].F.F <= en[v]){
            ++cnt;
            sv = v;
            idx = store[a[i]][it1].S;
          }
        }
        if(cnt == 0) update(st[i] , en[i],1);
        else if(cnt >= 2){
          update(st[1],  en[1] , 1);
        }
        else if(cnt == 1) {
          int sz = store[a[i]].size();
          if(store[a[i]][0].F.F >= st[i] && store[a[i]][sz-1].F.S <= en[i]){
            update(st[1] , en[1] , 1);
            update(st[i] , en[i] , -1);

            update(st[i], en[i] , 1);
            update(st[sv] , en[sv] , -1);

            update(st[idx] , en[idx] , 1);
          }
          else {
            update(st[1],  en[1] , 1);
          }
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; ++i) {
      sum[i] += sum[i-1];
      if(sum[i] == 0) {
        dbg(i);
        ++ans;
      }
    }
    cout << ans << endl;
    


    return 0;
}


