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 mz 1000000007

using namespace std;

int cnt=0;
map <int,int> mp;
vector <int> vec[200005],gg[200005];
int a[200005],dp[200005],dis[200005];
int fa[200005][20],ans=0;

void dfs(int x,int y)
{
    if(!mp[a[x]])
    {
        cnt++;
        mp[a[x]]=cnt;
    }
    gg[mp[a[x]]].push_back(x);
    dis[x]=y;
    for(int i=1;i<20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=0;i<vec[x].size();i++)
    {
        if(vec[x][i]!=fa[x][0])
        {
            fa[vec[x][i]][0]=x;
            dfs(vec[x][i],y+1);
        }
    }
}
void dfs1(int x)
{
    if(dp[x]==0)
        ans++;
    for(int i=0;i<vec[x].size();i++)
    {
        if(vec[x][i]!=fa[x][0])
        {
            dp[vec[x][i]]+=dp[x];
            dfs1(vec[x][i]);
        }
    }
}
int lca(int x,int y)
{
    for(int i=19;i>=0;i--)
    {
        if(dis[fa[x][i]]>=dis[y])
            x=fa[x][i];
    }
    for(int i=19;i>=0;i--)
    {
        if(dis[fa[y][i]]>=dis[x])
            y=fa[y][i];
    }
    for(int i=19;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            y=fa[y][i];
            x=fa[x][i];
        }
    }
    if(x!=y)
        x=fa[x][0];
    return x;
}
int go(int x,int y)
{
    for(int i=19;i>=0;i--)
    {
        if(dis[fa[y][i]]>=x)
            y=fa[y][i];
    }
    return y;
}

int main()
{
    int n,u,v,p;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(1,1);
    for(int i=1;i<=cnt;i++)
    {
        if(gg[i].size()>1)
        {
            u=gg[i][0];
            for(int j=1;j<gg[i].size();j++)
            {
                v=gg[i][j];
                p=lca(u,v);
                if(p==u)
                {
                    dp[v]++;
                    dp[1]++;
                    p=go(dis[u]+1,v);
                    dp[p]--;
                }
                else
                {
                    dp[u]++;
                    dp[v]++;
                    u=v;
                }
            }
        }
    }
    dfs1(1);
    printf("%d\n",ans);
    return 0;
}
