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 int long long
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 2e5 + 5;

int n, u, v, a[maxn], in[maxn], out[maxn], order[maxn], timer = -1, st[4 * maxn], need[4 * maxn];
vector<int> adj[maxn];
map<int, vector<int>> avals;

void dfs(int x, int p)
{
    in[x] = ++timer;
    order[timer] = x;
    avals[a[x]].push_back(x);
    for(auto v : adj[x])
        if(v != p)
            dfs(v, x);
    out[x] = timer;
}

int is_ancestor(int u, int v)
{
    return (in[u] <= in[v] && out[u] >= out[v]);
}

void build(int tl, int tr, int v)
{
    if(tl == tr)
        st[v] = 1;
    else
    {
        int tmid = (tl + tr) / 2;
        build(tl, tmid, 2 * v);
        build(tmid + 1, tr, 2 * v + 1);
        st[v] = 1;
    }
}

void push(int v)
{
    if(need[v])
    {
        st[2 * v] = st[2 * v + 1] = st[v];
        need[2 * v] = need[2 * v + 1] = need[v];
        need[v] = 0;
    }
}

void update(int tl, int tr, int l, int r, int v, int val)
{
    if(l > r)
        return;
    if(tl == l && tr == r)
    {
        st[v] = val;
        need[v] = 1;
    }
    else
    {
        push(v);
        int tmid = (tl + tr) / 2;
        update(tl, tmid, l, min(r, tmid), 2 * v, val);
        update(tmid + 1, tr, max(l, tmid + 1), r, 2 * v + 1, val);
    }
}

int get(int tl, int tr, int v, int pos)
{
    if(tl == tr)
    {
        assert(tl == pos);
        return st[v];
    }
    else
    {
        push(v);
        int tmid = (tl + tr) / 2;
        if(pos <= tmid)
            return get(tl, tmid, 2 * v, pos);
        else
            return get(tmid + 1, tr, 2 * v + 1, pos);
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n - 1; i++)
    {
        cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0, -1);
    build(0, n - 1, 1);
    for(auto x : avals)
        if(x.second.size() > 1)
        {
            for(int i = 0; i < x.second.size(); i++)
            {
                int pre = x.second[i];
                int cur = x.second[(i + 1) % x.second.size()];
                if(is_ancestor(cur, pre))
                    swap(cur, pre);
				if(is_ancestor(pre, cur))
                {
                    int pathchild = -1;
                    for(auto v : adj[pre])
                        if(is_ancestor(v, cur) && !is_ancestor(v, pre))
                        {
                            pathchild = v;
                            break;
                        }
					assert(pathchild != -1);
                    update(0, n - 1, 0, in[pathchild] - 1, 1, 0);
                    update(0, n - 1, out[pathchild] + 1, n - 1, 1, 0);
                    update(0, n - 1, in[cur], out[cur], 1, 0);
                }
                else
                {
                    update(0, n - 1, in[cur], out[cur], 1, 0);
                    update(0, n - 1, in[pre], out[pre], 1, 0);
                }
            }
        }
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += get(0, n - 1, 1, i);
    cout << ans << "\n";
    return 0;
}