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>
#include <map>
#include <algorithm> 
#include <vector> 
#include <string.h> 
#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <chrono> 
#include <thread> 
#include <iomanip>
#include <typeinfo>
 
//define
#define trav(i,v)   for(auto i: v)
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define all(v)  v.begin(), v.end()
#define itn int 
 
//typedef
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const long long MOD = 1000000007;
// const long long MOD = 998244353;
const long long inf = 1000000000000000000;
 
using namespace std;

ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll power(ll x, ll n)
{
    ll res=1;
    while(n>0){
        if(n&1) res=res*x;
        x=x*x;
        n>>=1;
    }
    return res;
}

void dfs(int x, vi *v, vi &vis, vi &euler, vi &a, vector<pair<pair<int, pair<int, int>>, pair<int, int>>> &info)
{
    int pos1 = euler.size();
    euler.pb(x);
    vis[x] = 1;
    int pos2 = -1;
    int start = pos1, end = pos1;
    vii v1;
    trav(y,v[x])
    {
        if(vis[y])
            continue;
        vis[y] = 1;
        dfs(y,v,vis,euler,a,info);
        pos2 = euler.size();
        euler.pb(x);
        // info.pb(mp(a[x],mp(pos1,pos2)));
        v1.pb(mp(pos1,pos2));
        end = pos2;
        pos1 = pos2;
    }
    if(pos2 == -1)
        info.pb(mp(mp(a[x],mp(start,end)),mp(pos1,pos1)));
    else
    {
        trav(p,v1)
        {
            info.pb(mp(mp(a[x],mp(start,end)),p));
        }
    }
    return;
}

void update(vi &v, int l, int r, int l1, int r1, int x)
{
    if(r<l1 || l>r1)
        return;
    if(r<=r1 && l>=l1)
    {
        // cout<<l<<" "<<r<<endl;
        v[x] = 0;
        return;
    }
    int m = (l+r)/2;
    update(v,l,m,l1,r1,2*x);
    update(v,m+1,r,l1,r1,2*x+1);
    return;
}

void lazy(vi &v, int l, int r, int x, int ch, vi &can, vi &euler)
{
    int m = (l+r)/2;
    if(v[x] == 0)
    {
        ch = 0;
    }
    if(ch == 0)
        v[x] = 0;
    if(l==r && ch==0)
    {
        // cout<<"a"<<l<<" "<<euler[l]<<" "<<v[x]<<endl;
        can[euler[l]] = ch;
        return;
    }
    else if(l==r)
        return;
    // cout<<l<<" "<<m<<" "<<m+1<<" "<<r<<endl;
    lazy(v,l,m,2*x,ch,can,euler);
    lazy(v,m+1,r,2*x+1,ch,can,euler);
    return;
}

int custom_sort(pair<pair<int, pair<int, int>>, pair<int, int>> p1, pair<pair<int, pair<int, int>>, pair<int, int>> p2)
{
    if(p1.fi.fi!=p2.fi.fi)
        return (p1.fi.fi<p2.fi.fi);
    return (p1.se<p2.se);
}

void solve()
{
    int n;
    cin>>n;
    vi a(n+1);
    int f = -1;
    repu(i,1,n)
    {
        cin>>a[i];
        if(f==-1)
            f = a[i];
    }
    vi v[n+1];
    repu(i,1,n-1)
    {
        int x, y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    vector<pair<pair<int, pair<int, int>>, pair<int, int>>> info;    
    vi euler, vis(n+1,0);
    euler.pb(0);
    dfs(1, v, vis, euler, a, info);
    int n1 = euler.size();
    n1--;
    sort(all(info),custom_sort);
    vector<int> seg(4*n1+5,1);
    int tmp = info.size();
    vi lev(tmp+3,-1);
    vi level(3,0);
    int max_r = 0;
    vi visited(n1+1,-1);
    // repu(i,1,n1)
    //     cout<<euler[i]<<" ";
    // cout<<endl;
    // rep(i,n)
    //     cout<<info[i].fi.fi<<" "<<info[i].se.fi<<" "<<info[i].se.se<<endl;
    rep(i,info.size())
    {
        if(i==0 || info[i].fi.fi != info[i-1].fi.fi)
        {
            if(level[2])
            {
                cout<<"0\n";
                return;
            }
            if(level[1] && level[0] > 1)
            {
                cout<<"0\n";
                return;
            }
            // cout<<i<<" "<<level[1]<<" "<<level[0]<<endl;
            level = vi(3,0);
            lev[i] = 0;
            level[0]++;
            max_r = info[i].se.se;
            visited[info[i].se.se] = lev[i];
            continue;
        }
        if(visited[info[i].se.fi]!=-1)
        {
            lev[i] = visited[info[i].se.fi];
            visited[info[i].se.se] = lev[i];
            if(info[i].se.se>max_r)
            {
                max_r = info[i].se.se;
            }
            continue;
        }
        if(info[i].se.fi<info[i-1].se.se)
        {
            lev[i] = lev[i-1]+1;
            level[lev[i]]++;
            if(level[2])
            {
                cout<<"0\n";
                return;
            }
            if(level[1] && level[0]>1)
            {
                cout<<"0\n";
                return;
            }
            visited[info[i].se.se] = lev[i];
            // cout<<info[i-1].se.fi<<" "<<info[i-1].se.se<<" "<<n1<<endl;
            update(seg,1,n1,1,info[i-1].se.fi,1);
            update(seg,1,n1,info[i-1].se.se,n1,1);
            update(seg,1,n1,info[i].fi.se.fi,info[i].fi.se.se,1);
        }
        else if(info[i].se.fi>info[i-1].se.se)
        {
            // cout<<"hi\n";
            if(info[i].se.fi>max_r)
            {
                max_r = info[i].se.se;
                lev[i] = 0;
                level[0]++;
                if(level[1] && level[0]>1)
                {
                    cout<<"0\n";
                    return;
                }
                visited[info[i].se.se] = lev[i];
                // cout<<info[i-1].se.fi<<" "<<info[i-1].se.se<<endl;
                // cout<<info[i].se.fi<<" "<<info[i].se.se<<endl;
                // lazy(seg,1,n1,1,1,tmpp,euler);
                update(seg,1,n1,info[i-1].fi.se.fi,info[i-1].fi.se.se,1);
                update(seg,1,n1,info[i].fi.se.fi,info[i].fi.se.se,1);
                // lazy(seg,1,n1,1,1,tmpp,euler);
            }
            else
            {
                lev[i] = 1;
                level[1]++;
                if(level[1] && level[0]>1)
                {
                    cout<<"0\n";
                    return;
                }
                visited[info[i].se.se] = lev[i];
                update(seg,1,n1,info[i-1].fi.se.fi,info[i-1].fi.se.se,1);
                update(seg,1,n1,info[i].fi.se.fi,info[i].fi.se.se,1);
            }
        }
        else
        {
            cout<<"Error\n";
            return;
        }
    }
    // repu(i,1,n1)
    //     cout<<euler[i]<<" ";
    // cout<<endl;
    if(level[2])
    {
        cout<<"0\n";
        return;
    }
    if(level[1] && level[0] > 1)
    {
        cout<<"0\n";
        return;
    }
    vi can(n+1,1);
    lazy(seg,1,n1,1,1,can,euler);
    // repu(i,1,n)
    // {
    //     cout<<can[i]<<" ";
    // }
    // cout<<endl;
    int cnt = 0;
    repu(i,1,n)
    {
        if(can[i])
            cnt++;
    }
    cout<<cnt<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1, tt=1;
    // cin>>t;    
    while(tt<=t)
    {
        // cout<<"Case #"<<tt<<": ";
        solve();
        tt++;
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}