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;

using ll = long long;
using pii = pair<ll, ll>;

#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define mk make_pair
#define F first
#define S second
#define debug(a) cout << #a << " = " << a << endl;
#define int long long

const int INF = 1000000009;
const ll MOD = 1000000007LL;

int n;
int a[200009];
vector<int> v[200009];

bool up[200009];
bool down[200009];
int cnt[200009];
map<int, int> sum;
map<int, vector<int>> r;

inline void Dfs(int u, int f) {
	r[a[u]].pb(u);
	
	set<int> s;
	for (auto i : v[u]) if (i != f) s.insert(i);
	
	cnt[u] = 1;
	int pre = cnt[u];
	for (auto i : v[u]) if (i != f) {
		Dfs(i, u);
		if (cnt[u] != pre) {
			up[u] = true;
			if (sz(s) == 0) continue;
			for (auto j : s) 
				if (j != i)
					down[j] = true;
			bool f = s.count(i);
			s.clear();
			if (f) s.insert(i);
			pre = cnt[u];
		}
	}
	
	if (cnt[u] != sum[a[u]]) down[u] = true;
	r[a[u]].pop_back();
	
	if (sz(r[a[u]]) != 0) cnt[r[a[u]].back()] += cnt[u];
}

inline void Dfs2(int u, int  f) {
	for (auto i : v[u]) if (i != f) Dfs2(i, u);
	
	set<int> s;
	for (auto i : v[u]) if (i != f && up[i] == true) s.insert(i);
	if (sz(s) == 0) return;
	if (sz(s) == 1) {
		for (auto i : v[u]) if (i != f && i != *s.begin()) down[i] = true;
	}
	else if (sz(s) >= 2) {
		for (auto i : v[u]) if (i != f) down[i] = true;
	}
	for (auto i : v[u]) if (i != f) up[u] |= up[i];
}

inline void Dfs3(int u, int f) {
	down[u] |= down[f];
	for (auto i : v[u]) if (i != f) Dfs3(i, u);
}

signed main() { IOS
	cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	for (int i = 1; i <= n - 1; ++ i) {
		int a, b;
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	for (int i = 1; i <= n; ++ i) sum[a[i]] += 1;
	Dfs(1, 1);
	Dfs2(1, 1);
	Dfs3(1, 1);
	
	int ans = 0;
	for (int i = 1; i <= n; ++ i) ans += (up[i] == 0 && down[i] == 0);
	cout << ans;
}