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 endl '\n'
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, mod = 1e9;
int n, a[N], cnt, id[N], diff[N], siz[N];
vector<int> G[N];
unordered_map<int, int> now, all;
void dfs(int u, int fa){
    siz[u] = 1;
    id[u] = ++cnt;
    ++now[a[u]];
    for(int v : G[u]){
        if(v == fa)continue;
        int x = now[a[u]], y = now[a[v]];
        dfs(v, u);
        siz[u] += siz[v];
        if(x < now[a[u]]){
            // v子树下有相同，删除
            ++diff[1];
            --diff[id[v]];
            ++diff[id[v] + siz[v]];
        }
        if(all[a[v]] - (now[a[v]] - y) > 0){ // v子树以外有相同，删除子树
            ++diff[id[v]];
            --diff[id[v] + siz[v]];
        }
    }
}
int main(){
    IOS;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        ++all[a[i]];
    }
    for(int x, y, i = 1; i < n; ++i){
        cin >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
    }
    dfs(1, 0);
    int ans = 0;
    for(int now = 0, i = 1; i <= n; ++i){
        now += diff[i];
        if(!now)++ans;
    }
    cout << ans << endl;
}
