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 rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lep(i,a,b) for(int i=(a);i>=(b);i--) 
#define sci(x) scanf("%d",&(x))
#define scl(x) scanf("%lld",&(x))
#define scs(x) scanf("%s",(x))
#define pri(x) printf("%d\n",(x))
#define prl(x) printf("%lld\n",(x))
#define prs(x) printf("%s\n",(x))
#define pii pair<int,int>
#define pll pair<long long,long long>
#define All(x) x.begin(),x.end() 
#define ms(a,b) memset(a,b,sizeof(a)) 
#define INF 0x3f3f3f3f
#define INFF 0x3f3f3f3f3f3f3f3f
#define multi int T;scanf("%d",&T);while(T--) 
using namespace std;
typedef long long ll;
typedef double db;
const int N=2e5+5;
const int mod=10007;
const db eps=1e-6;                                                                            
const db pi=acos(-1.0);
int n,cnt=0,a[N],dfn[N],sz[N],num[N];
map<int,int>mp1,mp2;
vector<int>tr[N];
void upd(int st,int ed,int val){
    num[st]+=val;
    num[ed+1]-=val;
}
void dfs(int u,int fa=-1){
    dfn[u]=++cnt;
    sz[u]=1;
    int tmp=mp2[a[u]];
    ++mp2[a[u]];
    for(auto v:tr[u]){
        if(v==fa) continue;
        int cur=mp2[a[u]];
        dfs(v,u);
        if(mp2[a[u]]!=cur){
            upd(dfn[v],dfn[v]+sz[v]-1,-1);
            upd(1,n,1);
        }
        sz[u]+=sz[v];
    }
    tmp=mp2[a[u]]-tmp;
    if(tmp<mp1[a[u]]) upd(dfn[u],dfn[u]+sz[u]-1,1);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("D:\\work\\data.in","r",stdin);
    #endif
    cin>>n;
    rep(i,1,n){
        cin>>a[i];
        ++mp1[a[i]];
    }
    rep(i,1,n-1){
        int x,y;
        cin>>x>>y;
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    dfs(1);
    int ans=0;
    rep(i,1,n){
        num[i]+=num[i-1];
        if(!num[i]) ++ans;
    }
    cout<<ans<<endl;
}