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 <iostream>
#include <bits/stdc++.h>
#define int long long
#define mk make_pair
#define gcd __gcd
using namespace std;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 3e5+7;
int n,m,k,t = 1,cas = 1;
int a[N],b[N];
//int cnt[N];     // 计数
//int vis[N];     // 计数
int in[N];      // dfs 进入序号
int out[N];     // dfs 退出序号
int sum[N];     // 差分数组
vector<int> edge[N];
vector<int> values;
map<int,int> cnt;
map<int,int> vis;
int tot = 0;

void dfs(int pos,int fa){
    in[pos] = ++tot;
    int cntt = vis[a[pos]] ++;
    for(int i = 0 ; i < edge[pos].size() ; i ++){
        int to = edge[pos][i];
        if(to == fa) continue;
        int now = vis[a[pos]];
        dfs(to,pos);
        if(vis[a[pos]] > now){
            sum[1] ++;
            sum[n+1] ++;
            sum[in[to]] --;
            sum[out[to]+1] ++;
        }
    }
    out[pos] = tot;
    if(vis[a[pos]] - cntt != cnt[a[pos]]){
        sum[in[pos]] ++;
        sum[out[pos]+1] --;
    }
}

signed main(){
    cin>>n;
    for(int i = 1 ; i <= n  ; i ++){
        cin>>a[i];
        values.push_back(a[i]);
    }
    for(int i = 0 ; i < n-1 ; i ++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    //sort(values.begin(),values.end());
    //values.erase(unique(values.begin(),values.end()),values.end());
    for(int i = 1 ; i <= n ; i ++){
        //a[i] = lower_bound(values.begin(),values.end(),a[i])-values.begin();
        cnt[a[i]] ++;
    }
    dfs(1,-1);
    int ans = 0;
    for(int i = 1; i <= n ; i ++){
        sum[i] += sum[i-1];
        if(sum[i] == 0){
            ans ++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
