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.
// coached by rainboy
import java.io.*;
import java.util.*;

public class CF1467E extends PrintWriter {
	CF1467E() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1467E o = new CF1467E(); o.main(); o.flush();
	}

	int[] eo; int[][] ej;
	void append(int i, int j) {
		int o = eo[i]++;
		if (o >= 2 && (o & o - 1) == 0)
			ej[i] = Arrays.copyOf(ej[i], o << 1);
		ej[i][o] = j;
	}
	int[] pp, ta, tb; int t;
	void dfs(int p, int i) {
		pp[i] = p;
		ta[i] = t++;
		for (int o = eo[i]; o-- > 0; ) {
			int j = ej[i][o];
			if (j != p)
				dfs(i, j);
		}
		tb[i] = t;
	}
	int[] ft;
	void update(int i, int n, int x) {
		while (i < n) {
			ft[i] += x;
			i |= i + 1;
		}
	}
	int query(int i) {
		int x = 0;
		while (i >= 0) {
			x += ft[i];
			i &= i + 1; i--;
		}
		return x;
	}
	int query2(int i) {
		return query(tb[i] - 1) - query(ta[i] - 1);
	}
	int[] dd;
	void mark(int a, int b) {
		dd[a]++; dd[b]--;
	}
	void main() {
		int n = sc.nextInt();
		int[] aa = new int[n];
		Integer[] ii = new Integer[n];
		for (int i = 0; i < n; i++) {
			aa[i] = sc.nextInt();
			ii[i] = i;
		}
		Arrays.sort(ii, (i, j) -> aa[i] - aa[j]);
		eo = new int[n]; ej = new int[n][2];
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			append(i, j);
			append(j, i);
		}
		pp = new int[n]; ta = new int[n]; tb = new int[n];
		dfs(-1, 0);
		ft = new int[n];
		dd = new int[n + 1];
		for (int i = 0, j; i < n; i = j) {
			int a = aa[ii[i]];
			j = i + 1;
			while (j < n && aa[ii[j]] == a)
				j++;
			if (j - i == 1)
				continue;
			for (int h = i; h < j; h++) {
				int u = ii[h];
				update(ta[u], n, 1);
			}
			for (int h = i; h < j; h++) {
				int u = ii[h];
				boolean yes = false;
				for (int o = eo[u]; o-- > 0; ) {
					int v = ej[u][o];
					if (v != pp[u] && query2(v) != 0) {
						yes = true;
						mark(0, ta[v]);
						mark(tb[v], n);
					}
				}
				if (yes) {
					if (query2(u) != j - i) {
						println(0);
						return;
					}
				} else
					mark(ta[u], tb[u]);
			}
			for (int h = i; h < j; h++) {
				int u = ii[h];
				update(ta[u], n, -1);
			}
		}
		int ans = 0;
		for (int d = 0, i = 0; i < n; i++)
			if ((d += dd[i]) == 0)
				ans++;
		println(ans);
	}
}
