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 mp make_pair
#define pb push_back
#define SZ(x) (int)(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int maxn = 1e6 + 6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int n,m;
int a[maxn],b[maxn],cnt[maxn],sum[maxn];
int dp[maxn];
int ans=0;
vector<int>G[maxn];
void dfs(int u,int fa) {
    cnt[a[u]]++;
    int x=cnt[a[u]],pre=x;
    for(int v:G[u]) {
        if(v!=fa) dfs(v,u);
        int cur=cnt[a[u]];
        if(cur!=pre) {
            dp[u]++;
            dp[v]--;
        }
        pre=cur;
    }
    int y=cnt[a[u]];
    if(y!=x) {
        dp[1]++;
        for(int v:G[u]) if(v!=fa) dp[v]--;
    }
    if(y-x+1!=sum[a[u]]) dp[u]++;
    // cout<<u<<','<<x<<','<<y<<','<<dp[u]<<endl;
}
void dfs(int u,int fa,int sum) {
    sum+=dp[u];
    //cout<<dp[u]<<','<<u<<'_'<<sum<<endl;
    if(sum==0) ans++;
    for(int v:G[u]) if(v!=fa) dfs(v,u,sum);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) {
        a[i]=lower_bound(b+1,b+1+m,a[i])-b;
        sum[a[i]]++;
    }
    dfs(1,0);
    dfs(1,0,0);
    printf("%d\n",ans);
    return 0;
}