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.
    /**   Created by: Humberto Yusta
          Codeforces User: humbertoyusta
          Country: Cuba
          Copyright��                    */
#include<bits/stdc++.h>
using namespace std;
/// Pragmas:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2") //Enable AVX
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 1000010;
const int mod = 1000000007;
const int mod2 = 998244353;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 1ll * mod * mod;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// rng
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return pwur * pwur % mod;
}
int modinv(int x){
    return qpow(x,mod-2);
}
/// My Code -------------------------------------------------

int n, tp[maxn], l[maxn], r[maxn], tcnt, res[maxn], par[maxn], arr[maxn];
vector<int> g[maxn], a[maxn];
vector<ii> compress;

bool fcmp(int u,int v){
    return l[u] < l[v];
}

void dfs(int u,int p){
    tp[++tcnt] = u;
    l[u] = r[u] = tcnt;
    par[u] = p;
    for( auto v : g[u] )
        if( v != p ){
            dfs(v,u);
            r[u] = max( r[u] , r[v] );
        }
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));

    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);

    cin >> n;

    bool can = 1;

    compress.pb({-1,-1});
    for(int i=1; i<=n; i++){
        cin >> arr[i];
        compress.pb({arr[i],i});
    }
    sort(all(compress));

    int curr = 0;
    for(int i=1; i<compress.size(); i++){
        if( compress[i].f != compress[i-1].f ) curr++;
        arr[compress[i].s] = curr;
    }

    for(int i=1; i<=n; i++){
        a[arr[i]].pb(i);
    }

    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs(1,1);

    for(int i=1; i<=n; i++)
        if( a[i].size() >= 2 )
            sort(a[i].begin(),a[i].end(),fcmp);

    for(int i=1; i<=n; i++){
        if( a[i].size() < 2 ) continue;
        for(int j=0; j<a[i].size(); j++){

            int nx = j + 1;
            if( nx >= a[i].size() )
                nx = 0;

            int u = a[i][j];
            int v = a[i][nx];
            if( l[u] > l[v] )
                swap( u , v );

//            db(u)db(v)
//            db(l[u])
//            db(r[u])
//            db(l[v])
//            db(r[v])
            if( l[u] <= l[v] && r[u] >= r[v] ){
                //if( a[i].size() >= 3 ) can = 0;
                res[l[v]]++;
                res[r[v]+1]--;
                for( auto w : g[u] ){
                    if( w == par[u] ) continue;
                    if( l[w] <= l[v] && r[w] >= r[v] ){
                        res[l[1]]++;
                        res[r[1]+1]--;
                        res[l[w]]--;
                        res[r[w]+1]++;
                    }
                }
            }
            else{
                res[l[u]]++;
                res[r[u]+1]--;
                res[l[v]]++;
                res[r[v]+1]--;
            }
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++){
        res[i] += res[i-1];
        ans += ( res[i] == 0 );
    }

    if( !can ) ans = 0;
    cout << ans << '\n';

    return 0;
}
