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 double ld;
typedef long long int ll;
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;

#define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define int long long
#define sz(v) (int)v.size()
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define f(i,l,r) for(long long i=l;i<=r;i++)
#define rf(i,r,l) for(long long i=r;i>=l;i--)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }


const int N = 2e5 + 5, mod = 1e9 + 7, bit = 61;

int tin[N], tout[N], tim = 0, n, a[N], val[N], ans = 0;
vector<int> adj[N], g[N];
map<int, int> mp;

void dfs(int u, int par)
{
	tin[u] = ++tim;
	for (auto &v : g[u])
	{
		if (v == par)
		{
			continue;
		}
		dfs(v, u);
	}
	tout[u] = tim;
}

void modify(int u, int par)
{
	int id = -1;
	int tot = 0;
	for (auto &v : g[u])
	{
		if (v == par)
		{
			continue;
		}
		modify(v, u);
		int cnt = (upper_bound(adj[a[u]].begin(), adj[a[u]].end(), tout[v]) - upper_bound(adj[a[u]].begin(), adj[a[u]].end(), tin[v] - 1));
		val[tin[u]] -= cnt;
		val[tout[u] + 1] += cnt;
		val[1] += cnt;
		val[n + 1] -= cnt;
		val[tin[v]] -= cnt;
		val[tout[v] + 1] += cnt;
	}
}

signed main()
{
	fast;


#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	cin >> n;
	f(i, 1, n)
	{
		cin >> a[i];
		mp[a[i]] = 1;
	}
	int id = 1;
	for (auto &x : mp)
	{
		x.ss = id++;
	}
	f(i, 1, n)
	{
		a[i] = mp[a[i]];
	}
	f(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1, 0);
	f(i, 1, n)
	{
		adj[a[i]].push_back(tin[i]);
	}
	f(i, 1, n)
	{
		sort(adj[i].begin(), adj[i].end());
	}
	f(i, 1, n)
	{
		int s = sz(adj[a[i]]) - 1;
		val[tin[i]] += s;
		val[tout[i] + 1] -= s;
	}
	modify(1, 0);
	f(i, 1, n)
	{
		val[i] += val[i - 1];
		ans += val[i] == 0;
	}
	cout << ans << endl;
	return 0;
}
