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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
const int N = 3e5 + 150;
const ll mod = 1e9 + 7;
const double Pi = acos(- 1.0);
const int INF = 0x3f3f3f3f;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

vector<int> sol;
int mp[N];
int head[N], cnt = 0;
int to[N << 1], nxt[N << 1];
int num[N], inum[N];
int val[N];
int dfn[N], tot = 0;
int ed[N];

void add(int u, int v){
    to[cnt] = v, nxt[cnt] = head[u], head[u] = cnt ++;
    to[cnt] = u, nxt[cnt] = head[v], head[v] = cnt ++;
}

void dfs(int u, int pre){
    dfn[u] = ++ tot;
    int tnum = num[mp[u]] ++;
    for(int i = head[u]; i != -1; i = nxt[i]){
        int v = to[i];
        if(v == pre) continue;
        int nownum = num[mp[u]];
        dfs(v, u);
        if(num[mp[u]] > nownum){
            val[1] ++;
            val[dfn[v]] --;
            val[ed[v] + 1] ++;
        }
    }
    ed[u] = tot;
    if(num[mp[u]] - tnum != inum[mp[u]]){
        val[dfn[u]] ++;
        val[ed[u] + 1] --;
    }
}


int main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    int n; scanf("%d",&n);
    for(int i = 1; i <= n; ++ i){
        head[i] = -1;
        scanf("%d",&mp[i]);
        sol.push_back(mp[i]);
    }
    sort(sol.begin(), sol.end());
    sol.erase(unique(sol.begin(), sol.end()), sol.end());
    for(int i = 1; i <= n; ++ i){
        mp[i] = lower_bound(sol.begin(), sol.end(), mp[i]) - sol.begin();
        inum[mp[i]] ++;
    }
    for(int i = 1; i < n; ++ i){
        int x, y; scanf("%d%d",&x,&y);
        add(x, y);
    }
    dfs(1, -1);
    int res = 0;
    for(int i = 1; i <= n; ++ i){
        val[i] += val[i - 1];
        if(val[i] == 0) res ++;
    }
    printf("%d\n",res);
    return 0;
}