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;

#define DIM 200009
#define INF ((int)1e18+9ll)
#define pairll pair<int,int>
#define fi first
#define se second
#define ld long double
#define MODULO1 998244353
#define MODULO2 1000000007
#define MODULO3 1000000009
#define MODULO 666013
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define amen exit(0)
#define endl '\n'
#define eps 0.00001
#define y1 trymax_lox
#define y2 djfkdjkafd
#define fxd(a) fixed<<setprecision(a)

long long i,j,k,l,n,m,x,timer,res;

long long tin[DIM],tout[DIM],col[DIM],c[DIM];

vector<pairll>a[DIM];
vector<long long>T[4*DIM];

map<long long,long long>mp;

void buildtree(long long v,long long tl,long long tr){
    if(tl==tr){
        T[v]={col[tl]};
        return;
    }

    long long tm=(tl+tr)/2;
    buildtree(v*2+1,tl,tm);
    buildtree(v*2+2,tm+1,tr);

    T[v].resize(T[v*2+1].size()+T[v*2+2].size());

    merge(T[v*2+1].begin(),T[v*2+1].end(),T[v*2+2].begin(),T[v*2+2].end(),T[v].begin());
}

long long check(long long v,long long tl,long long tr,long long L,long long R,long long x){
    if(L<=tl && tr<=R){
        auto p=equal_range(T[v].begin(),T[v].end(),x);
        return p.se-p.fi;
    }

    long long tm=(tl+tr)/2;
    if(R<=tm)return check(v*2+1,tl,tm,L,R,x);
    if(L>tm)return check(v*2+2,tm+1,tr,L,R,x);
    return check(v*2+1,tl,tm,L,R,x)+check(v*2+2,tm+1,tr,L,R,x);
}

void dfs1(long long v,long long p){
    tin[v]=++timer;
    col[timer]=c[v];

    for(auto to:a[v]){
        if(to.fi==p)continue;
        dfs1(to.fi,v);
    }

    tout[v]=timer;
}

long long dp[DIM],kilk;

long long dfs2(long long v,long long p){
    long long cnt=1,num=0,can=0;
    for(int i=0;i<a[v].size();i++){
        auto to=a[v][i];
        if(to.fi==p){
            num=i;
            continue;
        }
        can+=dfs2(to.fi,v);

        long long k=check(0,1,n,tin[to.fi],tout[to.fi],c[v]);

        if(k){
            cnt+=k;
            kilk++;
            a[v][i].se=1;
        }
    }
    dp[v]=can;

    if(cnt<mp[c[v]])a[v][num].se=1,kilk++,dp[v]++;

    return dp[v];
}

void dfs(long long v,long long p,long long cnt){
    long long curr=cnt;
    for(auto to:a[v]){
        if(to.fi==p)continue;
        curr+=dp[to.fi];
    }

    if(curr==kilk)res++;

    for(auto to:a[v]){
        if(to.fi==p)continue;
        dfs(to.fi,v,curr-dp[to.fi]+to.se);
    }
}

int main(){

    fast;

    long long root=0;
    cin>>n;
    for(i=1;i<=n;i++)cin>>c[i],mp[c[i]]++;

    for(i=1;i<n;i++){
        cin>>k>>l;
        a[k].push_back({l,0});
        a[l].push_back({k,0});
    }

    for(i=1;i<=n;i++){
        if(a[i].size()==1)root=i;
    }

//    cout<<root<<endl;

    dfs1(root,-1);

   // for(i=1;i<=n;i++)cout<<col[i]<<' ';
     //   cout<<endl;

//    cout<<"!"<<endl;

    buildtree(0,1,n);

    //cout<<check(0,1,n,2,4,1)<<endl;

    dfs2(root,-1);

    //cout<<kilk<<endl;

    dfs(root,-1,0);

    cout<<res<<endl;

    amen;
}
