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>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
typedef long long LL;
const int maxn = 2e5 + 5;

int cnt, id, a[maxn], hea[maxn], siz[maxn], dfsid[maxn], sum[maxn];

map<int, int> exist, tol;

struct node{
    int v, next;
}edge[maxn << 1];

inline void add(int u, int v){
    edge[++cnt].v = v;
    edge[cnt].next = hea[u];
    hea[u] = cnt;
}

inline void dfs(int u, int fa){
    siz[u] = 1;
    dfsid[u] = ++id;
    int pre = exist[a[u]]++;
    for(int k = hea[u]; k; k = edge[k].next){
        int v = edge[k].v;
        if(v == fa) continue;
        int x = exist[a[u]];
        dfs(v, u);
        siz[u] += siz[v];
        if(x != exist[a[u]]){			// 子树内出现了父节点的值，删除子树外所有点
            sum[1]++;
            sum[dfsid[v]]--;
            sum[dfsid[v] + siz[v]]++;
        }
    }
    if(exist[a[u]] - pre != tol[a[u]]){	// 子树外存在父节点的值，删除子树内所有点
        sum[dfsid[u]]++;
        sum[dfsid[u] + siz[u]]--;
    }
}

int main(){
    IOS;
    int n, u, v;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        tol[a[i]]++;
    }
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        sum[i] += sum[i - 1];
        ans += sum[i] == 0;
    }
    cout << ans << endl;
}

