1467_E. Distinctive Roots in a Tree
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.
```python
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)

    # Build euler tour
    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):
                # Subtour has non leaves, impossible
                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)):
                if segTree.query(i, i + 1) != 0:
                    print("x", end="\t")
                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))
```