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 <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
typedef long long ll;
vector<int>vec,G[maxn];
int a[maxn];
int sum[maxn],sta[maxn],ed[maxn],cnt;
int num[maxn]; //遍历过程每个数的出现次数
int NUM[maxn]; //初始每个数的出现次数

void dfs(int x,int fa) {
    sta[x] = ++cnt;
    int now_v = num[a[x]];
    ++num[a[x]];
    for(int i = 0;i < G[x].size();i++) {
        int v = G[x][i];
        if(v == fa) continue;
        int pre = num[a[x]];
        dfs(v,x);
        if(num[a[x]] > pre) { //这个子树有a[x]
            //x以及其他子树的点都非法
            sum[1]++;
            sum[sta[v]]--;
            sum[ed[v] + 1]++;
        }
    }
    ed[x] = cnt;
    if(num[a[x]] - now_v != NUM[a[x]]) { //连向父节点的子树有a[x]，那么x以及x对应其他子树非法
        sum[sta[x]]++;
        sum[ed[x] + 1]--;
    }
}
int main() {
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        vec.push_back(a[i]);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i = 1;i <= n;i++) {
        a[i] = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin();
        NUM[a[i]]++;
    }
    for(int i = 1;i < n;i++) {
        int x,y;scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,-1);
    int ans = 0;
    for(int i = 1;i <= n;i++) {
        sum[i] += sum[i - 1];
        if(sum[i] == 0) {
            ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}
