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;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 200005;

vector<int> G[N];
int a[N], d[N];
int dfn[N], out[N], ck;
map<int, int> mp, c;
void dfs(int u, int fa) {
    dfn[u] = ++ck;
    int tt = c[a[u]];
    c[a[u]]++;
    for (auto v : G[u]) {
        if (v == fa) continue;
        int tmp = c[a[u]];
        dfs(v, u);
        if (c[a[u]] > tmp) {
            d[1]++, d[dfn[v]]--;
            d[out[v] + 1]++;
        }
    }
    out[u] = ck;
    if (c[a[u]] - tt < mp[a[u]]) {
        d[dfn[u]]++, d[out[u] + 1]--;
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mp[a[i]]++;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    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;
}