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 int long long 
using namespace std;

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

const int M=2e5+10;
int n,a[M],d[M];
int dfn[M],out[M],ti;
vector<int>e[M];
map<int,int>c,t;

void dfs(int u,int fa)
{
    dfn[u]=++ti;
    int k=c[a[u]];c[a[u]]++;
    for (int i=0;i<e[u].size();i++)
    {
        int to=e[u][i];
        if (to==fa)continue;
        int tmp=c[a[u]];
        dfs(to,u);
        if (c[a[u]]>tmp)
            d[1]++,d[dfn[to]]--,d[out[to]+1]++;
    }
    out[u]=ti;
    if (c[a[u]]-k<t[a[u]])
        d[dfn[u]]++,d[out[u]+1]--;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read(),t[a[i]]++;
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);int ans=0;
    for (int i=1;i<=n;i++)
        d[i]+=d[i-1];
    for (int i=1;i<=n;i++)
        if (!d[i])ans++;
    cout<<ans<<endl;
    return 0;
}