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;
#define pb push_back

int root = 0;
int n;
int a[200200];
int parent[200200];
int rightmost_desc[200200];
vector<int> v[200200];
set<int> directed_edges[200200];

int preorder[200200];   // starts from 1
map<int, vector<int>> m;

int preorder_dfs(int x, int idx) {
    preorder[x] = idx++;
    for(int ch : v[x]) {
        if(preorder[ch] == 0) {
            v[ch].erase(remove(v[ch].begin(), v[ch].end(), x), v[ch].end());
            idx = preorder_dfs(ch, idx);
            parent[ch] = x;
        }
    }
    if(v[x].size() == 0)
        rightmost_desc[x] = x;
    else
        rightmost_desc[x] = rightmost_desc[v[x].back()];

    return idx;
}

int values_in_subtree(int x, int val) {
    int y = rightmost_desc[x];
    auto ptr1 = lower_bound(m[val].begin(), m[val].end(), preorder[x]);
    auto ptr2 = upper_bound(m[val].begin(), m[val].end(), preorder[y]);
    return ptr2-ptr1;
}

int distinctive_roots = 0;
void count_distinctive_roots(int x, int edges_outwards) {
    if(edges_outwards == 0)
        distinctive_roots++;
    for(int ch : v[x]) {
        bool outwards = (directed_edges[x].find(ch) != directed_edges[x].end());
        bool inwards = (directed_edges[ch].find(x) != directed_edges[ch].end());
        //cout << x << ": " << outwards << " " << inwards << " " << edges_outwards - outwards + inwards << "\n";
        count_distinctive_roots(ch, edges_outwards - outwards + inwards);
    }
}

void solve() {
    preorder_dfs(root, 1);     // use 0 as root

    for(int i = 0; i < n; i++)
        m[a[i]].pb(preorder[i]);
    for(auto& item : m)
        sort(item.second.begin(), item.second.end());

    int root_outwards_edges = 0;
    // find directed edges
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int ch : v[i]) {
            int count = values_in_subtree(ch, a[i]);
            if(count) {
                directed_edges[i].insert(ch);
                root_outwards_edges++;
            }
            sum += count;
        }
        if(i != root) {
            if(m[a[i]].size() > sum + 1) {
                directed_edges[i].insert(parent[i]);
            }
        }
    }

    //if(a[0] == 243075369)
    //    exit(997);
    
    // count distinctive roots
    //cout << "root_outwards_edges: " << root_outwards_edges << "\n";
    count_distinctive_roots(root, root_outwards_edges);

    cout << distinctive_roots << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        v[x].pb(y);
        v[y].pb(x);
    }

    solve();
}