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 ll long long
#define pii pair<int,int>
const int maxn = 2e5+5;
const int mx = 40;
const int mod = 1e9+5;
const ll inf = 34359738370;
const int INF = 1e9+5;
struct 
{
    int to,next;
}e[maxn<<1];
int head[maxn],cnt=0;
int in[maxn],out[maxn],tot=0;
int a[maxn],d[maxn];
int n;
map<int,int> all,temp; 
void add(int v,int u)
{
    e[++cnt].to=u;
    e[cnt].next=head[v];
    head[v]=cnt;
}
void dfs(int u,int fa)
{
    in[u]=++tot;
    int tt=temp[a[u]];
    temp[a[u]]++;
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa) continue;
        int now=temp[a[u]];
        dfs(to,u);
        if(temp[a[u]] > now)//to树中还有a[u]  把[1,in[to]-1]  [out[to]+1,n]
        {
            d[1]++,d[in[to]]--;
            d[out[to]+1]++;
        }
    }
    out[u]=tot;
    if(temp[a[u]] - tt <all[a[u]])//u树之外还有  修改u树区间
    {
        d[in[u]]++;
        d[out[u]+1]--;
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    // freopen("data.in.txt","r",stdin);
    // freopen("data.out.txt","w",stdout);
    #endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        all[a[i]]++;
    }
    for(int i=1;i<n;i++)
    {
        int v,u;scanf("%d %d",&v,&u);
        add(v,u),add(u,v);
    }
    dfs(1,0);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        d[i]+=d[i-1];
        if(!d[i]) ans++;
    }
    cout<<ans;
    return 0;
}