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 java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Iterator;
import java.util.HashMap;
import java.util.Stack;
import java.util.ArrayList;
import java.util.Vector;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sarthakmanna
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EDistinctiveRootsInATree solver = new EDistinctiveRootsInATree();
        solver.solve(1, in, out);
        out.close();
    }

    static class EDistinctiveRootsInATree {
        int N;
        long[] A;
        ArrayList<Integer>[] graph;
        HashMap<Long, myArrayListInteger> all;
        HLD_LCA hld;
        int[] parent;
        boolean[] down;
        boolean[] up;
        boolean[] curr;

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int i, j, k;

            N = in.nextInt();
            A = in.getLongArray(N);
            graph = new ArrayList[N];
            for (i = 0; i < N; ++i) graph[i] = new ArrayList<>();
            for (i = 1; i < N; ++i) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1;
                graph[a].add(b);
                graph[b].add(a);
            }

            hld = new HLD_LCA(graph, N, 0, A);
            parent = hld.getParent();
            all = hld.getSegmentTree().getMap();

            up = new boolean[N];
            down = new boolean[N];
            curr = new boolean[N];
            for (i = 0; i < N; ++i)
                if (all.get(A[i]).size() > 1) {
                    curr[i] = true;

                    int count = 0;
                    for (int itr : graph[i]) {
                        if (count(itr, i, A[i]) == 0) {
                            if (itr == parent[i]) up[i] = true;
                            else down[itr] = true;
                        } else {
                            ++count;
                        }
                    }
                    if (count > 1) {
                        System.out.println(0);
                        System.exit(0);
                    }
                }

            dfs(0, -7);
            dfsDown(0, -7);
            int ans = 0;
            for (i = 0; i < N; ++i) {
                if (up[i] || down[i]) curr[i] = true;
                if (!curr[i]) ++ans;
            }
            out.println(ans);
        }

        int count(int node, int forb, long color) {
            if (forb == parent[node]) {
                return hld.subtreeQuery(node, color);
            } else {
                return all.get(color).size() - hld.subtreeQuery(forb, color);
            }
        }

        void dfs(int node, int par) {
            int upCount = 0, upNode = -7;
            for (int itr : graph[node])
                if (itr != par) {
                    dfs(itr, node);
                    if (up[itr]) {
                        ++upCount;
                        upNode = itr;
                    }
                }
            if (upCount == 1) {
                curr[node] = true;
                for (int itr : graph[node])
                    if (itr != upNode && itr != par) {
                        down[itr] = true;
                    }
                up[node] = true;
            } else if (upCount > 1) {
                System.out.println(0);
                System.exit(0);
            }
        }

        void dfsDown(int node, int par) {
            if (par >= 0 && down[par]) down[node] = true;
            for (int itr : graph[node]) if (itr != par) dfsDown(itr, node);
        }

    }

    static class FastReader {
        static final int BUFSIZE = 1 << 20;
        static byte[] buf;
        static int index;
        static int total;
        static InputStream in;

        public FastReader(InputStream is) {
            try {
                in = is;
                buf = new byte[BUFSIZE];
            } catch (Exception e) {
            }
        }

        private int scan() {
            try {
                if (index >= total) {
                    index = 0;
                    total = in.read(buf);
                    if (total <= 0)
                        return -1;
                }
                return buf[index++];
            } catch (Exception | Error e) {
                System.err.println(e.getMessage());
                return 13 / 0;
            }
        }

        public int nextInt() {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

        public long nextLong() {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

        public long[] getLongArray(int size) {
            long[] ar = new long[size];
            for (int i = 0; i < size; ++i) ar[i] = nextLong();
            return ar;
        }

    }

    static class myArrayListInteger implements Iterable<Integer> {
        private int len;
        private int[] A;
        int itrInd;

        public myArrayListInteger(int initialLength) {
            A = new int[Math.max(1, initialLength)];
            len = 0;
        }

        public myArrayListInteger(myArrayListInteger src) {
            A = new int[src.A.length];
            System.arraycopy(src.A, 0, A, 0, src.len);
            len = src.len;
        }

        public void add(int ele) {
            if (len == A.length) {
                int[] newAr = new int[A.length << 1];
                System.arraycopy(A, 0, newAr, 0, len);
                A = newAr;
            }
            A[len++] = ele;
        }

        public int get(int ind) {
            if (ind >= len) throw new ArrayIndexOutOfBoundsException(ind);
            else if (ind < 0) ind += size();
            return A[ind];
        }

        public int size() {
            return len;
        }

        public boolean isEmpty() {
            return len == 0;
        }

        public int countFloor(int key) {
            // counts number of elements <= key provided this list is sorted
            if (isEmpty()) return 0;
            int l = 0, r = size() - 1, mid;
            while (true) {
                mid = l + r >> 1;
                if (l + 1 >= r) {
                    if (get(r) <= key) return r + 1;
                    else if (get(l) > key) return l;
                    else return r;
                } else if (get(mid) <= key) l = mid + 1;
                else r = mid;
            }
        }

        public Iterator<Integer> iterator() {
            itrInd = 0;
            Iterator<Integer> iterator = new Iterator<Integer>() {

                public boolean hasNext() {
                    return itrInd < size();
                }


                public Integer next() {
                    return get(itrInd++);
                }
            };
            return iterator;
        }

        public myArrayListInteger clone() {
            return new myArrayListInteger(this);
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len; i++) sb.append(A[i]).append(" ");
            return sb.toString().trim();
        }

    }

    static class Edge {
        int u;
        int v;
        long weight;

        public Edge(int a, int b, long wt) {
            u = a;
            v = b;
            weight = wt;
        }

        public String toString() {
            return "(" + u + ", " + v + " -> " + weight + ")";
        }

    }

    static class HLD_LCA {
        ArrayList<Integer>[] graph;
        int[] depth;
        int[] parent;
        int[] chCount;
        int[] queue;
        int N;
        int root;
        long[] weight;
        SegmentTree st;
        int[] treePos;
        int[] linearTree;
        int[] segRoot;

        public int[] getParent() {
            return parent;
        }

        public SegmentTree getSegmentTree() {
            return st;
        }

        public HLD_LCA(ArrayList<Integer>[] g, int[] dep, int[] par, int[] ch,
                       int n, int r, long[] wt) {
            graph = g;
            depth = dep;
            parent = par;
            chCount = ch;
            N = n;
            root = r;
            weight = wt;

            HLDify();
        }

        public HLD_LCA(ArrayList<Integer>[] g, int n, int r, long[] wt) {
            graph = g;
            N = n;
            root = r;
            weight = wt;
            iterativeDFS();

            HLDify();
        }

        public HLD_LCA(Edge[] edges, int n, int r) {
            int i;
            N = n;
            root = r;

            graph = new ArrayList[N];
            for (i = 0; i < N; ++i) graph[i] = new ArrayList<>();

            for (Edge e : edges) {
                graph[e.u].add(e.v);
                graph[e.v].add(e.u);
            }
            iterativeDFS();

            weight = new long[N];
            for (Edge e : edges) {
                int child = depth[e.u] > depth[e.v] ? e.u : e.v;
                weight[child] = e.weight;
            }

            HLDify();
        }

        private void iterativeDFS() {
            parent = new int[N];
            depth = new int[N];
            chCount = new int[N];
            queue = new int[N];
            Arrays.fill(chCount, 1);

            int i, st = 0, end = 0;
            parent[root] = -1;
            depth[root] = 1;
            queue[end++] = root;

            while (st < end) {
                int node = queue[st++], h = depth[node] + 1;
                Iterator<Integer> itr = graph[node].iterator();
                while (itr.hasNext()) {
                    int ch = itr.next();
                    if (depth[ch] > 0) continue;
                    depth[ch] = h;
                    parent[ch] = node;
                    queue[end++] = ch;
                }
            }
            for (i = N - 1; i >= 0; --i)
                if (queue[i] != root)
                    chCount[parent[queue[i]]] += chCount[queue[i]];
        }

        private void HLDify() {
            int i, j, treeRoot = -7;

            treePos = new int[N];
            linearTree = new int[N];
            segRoot = new int[N];

            Stack<Integer> stack = new Stack<>();
            stack.ensureCapacity(N << 1);
            stack.push(root);
            for (i = 0; !stack.isEmpty(); ++i) {
                int node = stack.pop();
                if (i == 0 || linearTree[i - 1] != parent[node])
                    treeRoot = node;
                linearTree[i] = node;
                treePos[node] = i;
                segRoot[node] = treeRoot;

                int bigChild = -7, bigChildPos = -7, lastPos = graph[node].size() - 1;
                for (j = 0; j < graph[node].size(); ++j) {
                    int tempNode = graph[node].get(j);
                    if (tempNode == parent[node]) continue;
                    if (bigChild < 0 || chCount[bigChild] < chCount[tempNode]) {
                        bigChild = tempNode;
                        bigChildPos = j;
                    }
                }
                if (bigChildPos >= 0) {
                    int temp = graph[node].get(lastPos);
                    graph[node].set(lastPos, bigChild);
                    graph[node].set(bigChildPos, temp);
                }

                for (int itr : graph[node])
                    if (parent[node] != itr)
                        stack.push(itr);
            }

            long[] respectiveWeights = new long[N];
            for (i = 0; i < N; ++i)
                respectiveWeights[i] = weight[linearTree[i]];
            st = new SegmentTree(respectiveWeights);
        }

        public int subtreeQuery(int node, long key) {
            int pos = treePos[node];
            return st.rangeQuery(pos, pos + chCount[node] - 1, key); // ...(pos + 1,... for Edge Query
        }

    }

    static class SegmentTree {
        HashMap<Long, myArrayListInteger> map;

        public HashMap<Long, myArrayListInteger> getMap() {
            return map;
        }

        public SegmentTree(long[] ar) {
            map = new HashMap<>();
            for (int i = 0; i < ar.length; ++i) {
                map.putIfAbsent(ar[i], new myArrayListInteger(1));
                map.get(ar[i]).add(i);
            }
        }

        public int rangeQuery(int l, int r, long key) {
            myArrayListInteger list = map.get(key);
            return list.countFloor(r) - list.countFloor(l - 1);
        }

    }
}

