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.
/*
 * @file E.cpp
 * @path D:\code\ACM\codeforces\Div2_695\E.cpp
 * @author Xiuchen
 * @date  2021-01-18 00:53:37
*/

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<cmath>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
//#define DEBUG
#define M_PI 3.14159265358979323846
#define dbg(x) cout << #x << " = "<< (x) << endl
#define dbg2(x1,x2) cout << #x1 << " = " << x1 << " " << #x2 << " = " << x2 << endl
#define dbg3(x1,x2,x3) cout<< #x1 << " = " << x1 << " " << #x2 << " = " << x2 << " " << #x3 << " = " << x3 <<endl
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 2e5 + 100;
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int n, a[maxn], lsh[maxn], tot[maxn], sum[maxn], sz[maxn];
int dfn[maxn], cnt = 0, d[maxn];
vector<int> G[maxn];
void update(int l, int r, int k){
    if(l > r) return;
    d[l] += k; d[r + 1] -= k;
}
void dfs(int x, int fa){
    sz[x] = 1; dfn[x] = ++cnt; 
    int cur = sum[a[x]]; sum[a[x]]++;
    for(int i = 0; i < G[x].size(); i++){
        int y = G[x][i];
        if(y == fa) continue;
        int tmp = sum[a[x]];
        dfs(y, x);
        sz[x] += sz[y];
        if(sum[a[x]] > tmp){
            update(1, n, 1);
            update(dfn[y], dfn[y] + sz[y] - 1, -1);
        }
    }
    cur = sum[a[x]] - cur;
    if(cur < tot[a[x]]) update(dfn[x], dfn[x] + sz[x] - 1, 1);
}
int main(){
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif  
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), lsh[i] = a[i];
    for(int i = 1; i <= n - 1; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    sort(lsh + 1, lsh + n + 1);
    int lshnum = unique(lsh + 1, lsh + n + 1) - lsh - 1;
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(lsh + 1, lsh + lshnum + 1, a[i]) - lsh;
        tot[a[i]]++;
    }
    d[0] = 0;
    dfs(1, 0);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        d[i] += d[i - 1];
        if(d[i] == 0) ans++;
    }
    printf("%d\n", ans);
    return 0;
}