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.
//
// Created by mihai145 on 26.02.2021.
//

#include <iostream>
#include <vector>
#include <map>
#include <set>

#include <cassert>

using namespace std;

const int NMAX = 2e5;
const int LGMAX = 20;

int N;
int color[NMAX + 5];

vector<int> g[NMAX + 5];
vector<int> ofColor[NMAX + 5];

int k;
map<int, int> normalizedColors;

int firstAp[NMAX + 5], h[NMAX + 5];
int log2[2 * NMAX + 5];
vector<int> rmq[LGMAX + 5];

int lift[NMAX + 5][LGMAX];

//int _time;
//int timeIn[NMAX + 5], timeOut[NMAX + 5];

int par[NMAX + 5];

void initTree(int node, int parent = 0) {
    firstAp[node] = (int) rmq[0].size();
    rmq[0].push_back(node);

    par[node] = parent;
    lift[node][0] = parent;

//    _time++;
//    timeIn[node] = _time;

    for (int son : g[node]) {
        if (son != parent) {
            h[son] = h[node] + 1;
            initTree(son, node);
            rmq[0].push_back(node);
        }
    }

//    _time++;
//    timeOut[node] = _time;
}

int GetMinH(int x, int y) {
    if (h[x] < h[y]) {
        return x;
    }

    return y;
}

void initRmq() {
    log2[1] = 0;
    for (int i = 2; i <= 2 * N; i++) {
        log2[i] = 1 + log2[i / 2];
    }

    for (int i = 1; i <= LGMAX; i++) {
        if ((1 << i) > (int) rmq[0].size()) {
            break;
        }
        for (int j = 0; j < (int) rmq[0].size(); j++) {
            if (j + (1 << i) > (int) rmq[0].size()) {
                break;
            } else {
                rmq[i].push_back(GetMinH(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
            }
        }
    }
}

int queryRmq(int x, int y) {
    x = firstAp[x];
    y = firstAp[y];

    if (x > y) {
        swap(x, y);
    }

    int k = log2[y - x + 1];
    return GetMinH(rmq[k][x], rmq[k][y - (1 << k) + 1]);
}

void initLift() {
    for (int i = 1; i < LGMAX; i++) {
        for (int v = 1; v <= N; v++) {
            lift[v][i] = lift[lift[v][i - 1]][i - 1];
        }
    }
}

//bool isAncestor(int x, int y) {
//    if(timeIn[x] < timeIn[y] && timeOut[y] < timeOut[x]) {
//        return true;
//    }
//
//    return false;
//}

bool depleted[NMAX + 5];

void DfsFill(int node, int parent) {
    if (depleted[node] == true) {
        return;
    }

    depleted[node] = true;

    for (int son : g[node]) {
        if (son != parent) {
            DfsFill(son, node);
        }
    }
}

void Fill(int A, int B) {
    int lca = queryRmq(A, B);

    if (A == lca) {
        DfsFill(B, par[B]);

        int sonLca = B;
        for (int step = LGMAX - 1; step >= 0; step--) {
            if (h[lift[sonLca][step]] > h[lca]) {
                sonLca = lift[sonLca][step];
            }
        }

        DfsFill(lca, sonLca);
        assert(lca == par[sonLca]);

//        for(int it : g[lca]) {
//            if(it != par[lca] && isAncestor(it, B)) {
//                DfsFill(lca, it);
//                break;
//            }
//        }
    } else if (B == lca) {
        DfsFill(A, par[A]);

        int sonLca = A;
        for (int step = LGMAX - 1; step >= 0; step--) {
            if (h[lift[sonLca][step]] > h[lca]) {
                sonLca = lift[sonLca][step];
            }
        }

        DfsFill(lca, sonLca);
        assert(lca == par[sonLca]);

//        for(int it : g[lca]) {
//            if(it != par[lca] && isAncestor(it, A)) {
//                DfsFill(lca, it);
//                break;
//            }
//        }
    } else {
        DfsFill(A, par[A]);
        DfsFill(B, par[B]);
    }
}

bool ans;
multiset<int> seenColors;

void Check(int node, int parent = 0) {
    if (seenColors.find(color[node]) != seenColors.end()) {
        ans = false;
        return;
    }

    if (ans == false) {
        return;
    }

    seenColors.insert(color[node]);

    for (int son : g[node]) {
        if (son != parent) {
            Check(son, node);
        }
    }

    seenColors.erase(seenColors.find(color[node]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> color[i];
        if (!normalizedColors[color[i]]) {
            normalizedColors[color[i]] = ++k;
        }
        ofColor[normalizedColors[color[i]]].push_back(i);
    }

    for (int i = 1; i < N; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    initTree(1);
    initRmq();
    initLift();

    for (int i = 1; i <= k; i++) {
        if ((int) ofColor[i].size() > 1) {
            for (int j = 1; j < (int) ofColor[i].size(); j++) {
                Fill(ofColor[i][0], ofColor[i][j]);
            }
        }
    }

    int ct = 0, nonDepleted = -1;
    for (int i = 1; i <= N; i++) {
        if (!depleted[i]) {
            ct++;
            nonDepleted = i;
        }
    }

    if (nonDepleted == -1) {
        cout << 0 << '\n';
    } else {
        ans = true;
        Check(nonDepleted);
        if (ans == true) {
            cout << ct << '\n';
        } else {
            cout << 0 << '\n';
        }
    }

    return 0;
}