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.
//November
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=3e5;
vector<int>G[maxn],v;
int dp[maxn];
int a[maxn];
map<int,int>num,sta;
void dfs(int x,int f)
{
    int base=sta[a[x]];
    sta[a[x]]++;
    for(int i=0;i<G[x].size();i++)
    {
        int t=G[x][i];
        if(t==f)
            continue;
        int tmp=sta[a[x]];
        dfs(t,x);
        if(tmp!=sta[a[x]])
            dp[1]++,dp[t]--;
    }
    if(sta[a[x]]-base!=num[a[x]])
        dp[x]++;
}
int ans;
void solve(int x,int f,int now)
{
    if(now==0)
        ans++;
    for(int i=0;i<G[x].size();i++)
    {
        int t=G[x][i];
        if(t==f)
            continue;
        solve(t,x,now+dp[t]);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
        num[a[i]]++;
    }
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,0);
    solve(1,0,dp[1]);
    cout<<ans<<endl;
}
