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.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define X first
#define Y second
#define pb push_back
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pii pair<int,int>
#define New_Time srand((unsigned)time(NULL))
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
int head[2000010], Edge_Num;
struct Edge { int to, next; ll w; }e[4000010];
inline void ade(int x, int y, ll w) { e[++Edge_Num] = { y,head[x],w }; head[x] = Edge_Num; }
inline void G_init(int n) { memset(head, 0, sizeof(int) * (n + 100)); Edge_Num = 0; }
int dir[8][2] = { {-1,0},{0,-1},{-1,-1},{1,-1},{1,0},{0,1},{1,1},{-1,1} };
const long double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline void pt(ll x) { printf("%lld\n", x); }
inline void pt(int x) { printf("%d\n", x); }
inline ll rd() {
	ll x = 0; bool f = 1; char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-')f = 0; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
	return f ? x : -x;
}
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const int M = 1e6 + 10;
const int N = 2e5 + 10;
vector<int>ver[N];
bool f[N];
int a[N], siz[N], fa[N], cnt[N], sum[N], son[N], num, L[N], R[N], dfn[N];
map<int, bool>mp[N];
void discreat(int n) {
	vector<int>ve;
	for (int i = 1; i <= n; i++)ve.pb(a[i]);
	sort(ve.begin(), ve.end());
	ve.erase(unique(ve.begin(), ve.end()), ve.end());//离散化
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(ve.begin(), ve.end(), a[i]) - ve.begin() + 1;
	}
}
void dfs0(int x) {
	f[x] = 1, siz[x] = 1, L[x] = ++num, dfn[num] = x, sum[a[x]]++;
	for (auto& y : ver[x]) {
		if (y == fa[x])continue;
		fa[y] = x;
		dfs0(y);
		siz[x] += siz[y];
		if (!son[x] || siz[y] > siz[son[x]])son[x] = y;
	}
	R[x] = num;
}
int ans;
bool add(int x, int k, int rt) {
	bool fg = 1;
	for (int i = L[x]; i <= R[x]; i++) {
		int y = dfn[i];
		cnt[a[y]] += k;
		if (k == 1 && a[rt] == a[y])fg = 0;
	}
	return fg;
}
void dsu(int x, bool del) {
	for (auto& y : ver[x]) {
		if (y == fa[x] || y == son[x])continue;
		dsu(y, 1);
	}
	if (son[x]) {
		dsu(son[x], 0);
		if (mp[son[x]].size() || cnt[a[x]])mp[x][son[x]] = 1;
	}
	for (auto& y : ver[x]) {
		if (y == fa[x] || y == son[x])continue;
		if (!add(y, 1, x) || mp[y].size())mp[x][y] = 1;
	}
	cnt[a[x]]++;
	if (cnt[a[x]] < sum[a[x]])f[x] = 0;
	if (del)add(x, -1, x);
}
bool ok[N];
void dfs(int x) {
	if (!mp[x].size() && f[x] &&
		(mp[fa[x]].size() == 0 || mp[fa[x]].size() == 1 
			&& mp[fa[x]].count(x)))++ans;
	for (auto& y : ver[x]) {
		if (y == fa[x])continue;
		f[y] &= f[x];
		if (mp[x].size() > 1 || mp[x].size() == 1 && !mp[x].count(y))f[y] = 0;
		dfs(y);
	}
}
void solve() {
	int n = rd();
	for (int i = 1; i <= n; i++)a[i] = rd();
	for (int i = 1; i < n; i++) {
		int u = rd(), v = rd();
		ver[u].pb(v), ver[v].pb(u);
	}
	discreat(n);
	dfs0(1);
	ans = 0;
	dsu(1, 1);
	dfs(1);
	pt(ans);
}
int main() {
	int T = 1;
	//T = rd();
	while (T--)solve();
}