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.
/// Get Down with The Sickness
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

using ll = long long;
using ii = pair<int, int>;


const int N = 2e5 + 5, LG = 19, MOD = 1e9 + 7;
using mat = vector<vector<long double>>;
void printCase(int cs) {
    cout << "Case #" << cs << ": ";
}
int n;
int a[200005];
map<int, int> mp, cnt;
vector<int> adj[200005];
int in[N], out[N], sum[N], dfsTimer;
void dfs(int node, int par) {
    in[node] = dfsTimer++;
    int tmp = mp[a[node]];
    mp[a[node]] += 1;

    for(auto to : adj[node])
    if(to != par) {
        int cur = mp[a[node]];
        dfs(to, node);
        if(mp[a[node]] > cur) {
            sum[0]++;
            sum[in[to]]--;
            sum[out[to]]++;
        }
    }
    out[node] = dfsTimer;
    if(cnt[a[node]] > mp[a[node]] - tmp) {
        sum[in[node]] += 1;
        sum[out[node]] -= 1;
    }
}
int main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE

    cin >> n;
    f(i,1,n+1)  cin >> a[i], cnt[a[i]]++;


    f(i,1,n) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs(1, 1);

    int ans = sum[0] == 0;
    f(i,1,n){
        sum[i]+=sum[i-1];
        ans += sum[i] == 0;
    }

    cout << ans << '\n';

    return 0;
}


