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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.Vector;

public class Codeforces1467E {
	interface DFS {
		void init(int x, int p);

		void solve(int x, int p);
	}

	static void task(FastReader input, PrintWriter output) {
		final int n = input.nextInt();

		var a = new int[n];
		var adj = Util.get2DimVector(n);
		var map = new TreeMap<Integer, Integer>();

		for (int i = 0; i < n; ++i) {
			a[i] = input.nextInt();
			map.putIfAbsent(a[i], map.size());
			a[i] = map.get(a[i]);
		}

		for (int i = 0; i < n - 1; ++i) {
			int u = input.nextInt() - 1;
			int v = input.nextInt() - 1;
			adj.get(u).addElement(v);
			adj.get(v).addElement(u);
		}

		var ti = new int[n];
		var to = new int[n];
		var notDistinct = new boolean[n];
		var tim = Util.get2DimVector(map.size());

		var dfs = new DFS() {
			int timer = 0;
			int solution = 0;

			public void init(int x, int p) {
				ti[x] = timer++;
				tim.get(a[x]).addElement(ti[x]);
				for (int y : adj.get(x)) {
					if (y != p) {
						init(y, x);
						notDistinct[x] |= notDistinct[y];
					}
				}
				to[x] = timer;
				if (Util.lowerBound(tim.get(a[x]), to[x]) != Util.lowerBound(tim.get(a[x]), ti[x] + 1)) {
					notDistinct[x] = true;
				}
			}

			public void solve(int x, int p) {
				int count_ch = 0;
				for (int y : adj.get(x)) {
					count_ch += notDistinct[y] ? 1 : 0;
				}
				notDistinct[x] = count_ch > 0 || tim.get(a[x]).size() > 1;
				solution += notDistinct[x] ? 0 : 1;
				for (int y : adj.get(x)) {
					if (y != p) {
						int count_del = Util.lowerBound(tim.get(a[x]), to[y]) - Util.lowerBound(tim.get(a[x]), ti[y]);
						if (tim.get(a[x]).size() - count_del == 1 && count_ch - (notDistinct[y] ? 1 : 0) == 0) {
							notDistinct[x] = false;
						}
						solve(y, x);
						notDistinct[x] = count_ch > 0 || tim.get(a[x]).size() > 1;
					}
				}
			}
		};

		dfs.init(0, -1);
		dfs.solve(0, -1);
		System.out.println(dfs.solution);
	}

	public static void main(String[] args) {
		long startTime = System.nanoTime();
		var input = new FastReader();
		var output = new PrintWriter(System.out);
		int t = 1;
		while (t-- > 0) {
			task(input, output);
		}
		output.flush();
		long stopTime = System.nanoTime();
		System.err.printf("TIME: %f sec\n", (stopTime - startTime) / 1e9);
	}

	static class Util {
		static <E> int lowerBound(Vector<E> vector, Comparable<E> obj) {
			int lo = 0;
			int hi = vector.size();
			while (lo < hi) {
				int mid = (lo + hi) / 2;
				if (obj.compareTo(vector.get(mid)) > 0) {
					lo = mid + 1;
				} else {
					hi = mid;
				}
			}
			return lo;
		}

		static Vector<Vector<Integer>> get2DimVector(int sz) {
			var ret = new Vector<Vector<Integer>>(0);
			ret.setSize(sz);
			ret.replaceAll(x -> new Vector<>(0));
			return ret;
		}
	}

	static class FastReader {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		String next() {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(nextLine());
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			try {
				return br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return "";
		}
	}

}