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.
import io, os;from collections import Counter, defaultdict, deque

class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        _default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        q, self._lazy[idx] = self._lazy[idx], 0

        self._lazy[2 * idx] += q
        self._lazy[2 * idx + 1] += q
        self.data[2 * idx] += q
        self.data[2 * idx + 1] += q

    def _update(self, idx):
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        idx >>= 1
        while idx:
            self.data[idx] = (
                self._func(self.data[2 * idx], self.data[2 * idx + 1]) + self._lazy[idx]
            )
            idx >>= 1

    def add(self, start, stop, value):
        if start == stop:
            return
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] += value
                self.data[start] += value
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] += value
                self.data[stop] += value
            start >>= 1
            stop >>= 1
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=0):
        start += self._size
        stop += self._size
        self._update(start)
        self._update(stop - 1)

        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)


def solve(N, A, edges):
    graph = [[] for i in range(N)]
    for u, indices in edges:graph[u].append(indices);graph[indices].append(u)
    eulerTour = [];root = 0;stack = [root];seen = [False] * len(graph)
    while stack:
        node = stack.pop();eulerTour.append(node)
        if not seen[node]:
            seen[node] = True
            for nbr in graph[node]:
                if not seen[nbr]:stack.append(node);stack.append(nbr)
    assert eulerTour[0] == eulerTour[-1];eulerTour.pop();tourByValues = defaultdict(list)
    for i, x in enumerate(eulerTour):tourByValues[A[x]].append(i)
    segTree = LazySegmentTree([0] * len(eulerTour), 0, lambda x, y: x + y)
    for k, indices in tourByValues.items():
        nodes = set(eulerTour[i] for i in indices)
        if len(nodes) >= 2:
            for i in indices:segTree.add(i, i + 1, 1)
            subtour = []
            for i, j in zip(indices, indices[1:]):
                x = eulerTour[i];y = eulerTour[j]
                if x == y:segTree.add(i, j + 1, 1)
                else:subtour.append(i)
            i = indices[-1];j = indices[0];x = eulerTour[i];y = eulerTour[j]
            if x == y:segTree.add(i, len(eulerTour), 1);segTree.add(0, j + 1, 1)
            else:subtour.append(i)
            if len(nodes) != len(subtour):return 0
        if False:
            print("label", k, "visits", indices, "nodes", nodes);print("\t".join(str(eulerTour[i]) + ":" + str(A[eulerTour[i]]) for i in range(len(eulerTour))))
            for i in range(len(eulerTour)):print("x", end="\t") if segTree.query(i, i + 1) != 0 else print("o", end="\t")
            print();print()
    return N - len(set([eulerTour[i] for i in range(len(eulerTour)) if segTree.query(i, i + 1) != 0]))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N = int(input());A = [int(x) for x in input().split()];e = [[int(x) - 1 for x in input().split()] for i in range(N - 1)];print(solve(N, A, e))