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;

const int maxn = 200050;
int n, dfn, ans;
int a[maxn], in[maxn], out[maxn], par[maxn], dp[maxn];

vector<int> G[maxn];
set<pair<int, int>> e;
map<int, vector<int>> mp;

void dfs(int rt, int fa)
{
    in[rt] = ++dfn;
    for (auto i : G[rt]) {
        if (fa == i)
            continue;
        par[i] = rt;
        dfs(i, rt);
    }
    out[rt] = ++dfn;
}

void getans(int rt)
{
    dp[rt] = 0;
    for (auto i : G[rt]) {
        if (i == par[rt])
            continue;
        getans(i);
        dp[rt] += dp[i] + e.count(make_pair(i, rt));
    }
}

void changeroot(int rt)
{
    if (dp[rt] == (int)e.size())
        ans++;
    for (auto i : G[rt]) {
        if (i == par[rt])
            continue;
        dp[rt] -= dp[i];
        dp[rt] -= e.count(make_pair(i, rt));
        dp[i]  += dp[rt];
        dp[i]  += e.count(make_pair(rt, i));
        
        changeroot(i);

        dp[i]  -= e.count(make_pair(rt, i));
        dp[i]  -= dp[rt];
        dp[rt] += e.count(make_pair(i, rt));
        dp[rt] += dp[i];
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mp[a[i]].emplace_back(i);           // 使用 map 来保存每个权值出现的编号
    }
    for (int i = 0, u, v; i < n-1; i++) {
        scanf("%d%d", &u, &v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 0);                              // 以 1 为根，先序遍历求 dfn
    for (auto tmp : mp) {                   // 考虑所有出现过的点权 a[u]
        if (tmp.second.size() == 1)
            continue;                       // 对应权值 a[u] 的点只有一个，必然不可能出现重复

        vector<int> indfn;
        for (auto x : tmp.second)
            indfn.emplace_back(in[x]);      // 把对应权值为 a[x] 点的 DFS 序加入数组
        sort(indfn.begin(), indfn.end());

        for (auto x : tmp.second) {
            int tot = 0;
            for (auto y : G[x]) {           // 计算 x 的子树（不包含 x）中出现过 a[x] 的次数
                if (y == par[x])
                    continue;
                int count = upper_bound(indfn.begin(), indfn.end(), out[y])
                          - lower_bound(indfn.begin(), indfn.end(), in[y]);
                                            // 统计节点中包含相同点的个数
                if (count > 0)
                    e.insert(make_pair(x, y));          // 如果存在则连边
                tot += count;
            }
            tot++;

            int rest = (int)tmp.second.size() - tot;
            if (rest > 0)
                e.insert(make_pair(x, par[x]));         // 考虑父节点
        }
    }
    getans(1);
    changeroot(1);
    printf("%d", ans);
    return 0;
}
