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>
 
#define dbg(x) cerr << #x << " == " << x << endl
#define _ << " , " <<
 
using namespace std;
 
template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }

const int maxn = 2e5 + 100;

struct Edge {
  int from, to, bad, next;
} edge[2*maxn];
int nedge = 0;

int n;
int a[maxn];
int mark[maxn];
int adj[maxn];
int seen[maxn];
int total[maxn];
int f[maxn];
int tmp[maxn];

void dfs(int node, int parent, int eid) {
  int count = seen[a[node]];

  // parent -> node is bad!
  if (count > 0) {
    edge[eid^1].bad |= mark[a[node]];
  }

  for(int e = adj[node]; e >= 0; e = edge[e].next) {
    int to = edge[e].to;
    if (to == parent) continue;
    dfs(to, node, e);
    int newCount = seen[a[node]];
    if (newCount > count) { // edge (node, next) is bad
      count = newCount;
      edge[e].bad |= mark[a[node]];
    }
  }

  seen[a[node]]++;

  // parent -> node is bad?
  int left = total[a[node]] - seen[a[node]];
  if (left > 0) {
    edge[eid^1].bad |= mark[a[node]];
  }
}

void dfs2(int node, int parent) {
  f[node] = 1;

  int ptr = -1;
  for (int e = adj[node]; e >= 0; e = edge[e].next) {
    int to = edge[e].to;
    if (to == parent) {
      ptr = e;
      continue;
    }
    dfs2(to, node);
  }

  adj[node] = ptr;
 
  if (ptr != -1) {
    edge[ptr].next = -1;
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];

  for(int i = 1; i <= n; i++) adj[i] = -1;

  for(int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    {
      int ptr = adj[u];
      edge[nedge] = (Edge){u,v,0,ptr};
      adj[u] = nedge++;
    }
    {
      int ptr = adj[v];
      edge[nedge] = (Edge){v,u,0,ptr};
      adj[v] = nedge++;
    }
  }

  // compress
  {
    for(int i = 1; i <= n; i++) tmp[i-1] = a[i];
    sort(tmp, tmp + n);
    int bsize = unique(tmp, tmp + n) - tmp;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(tmp, tmp + bsize, a[i]) - tmp;
  }

  for (int i = 0; i <= n; i++) mark[i] = -1;

  for (int i = 1; i <= n; i++) {
    total[a[i]]++;
    mark[a[i]]++;
  }

  dfs(1, -1, -1);

  for (int i = 0; i < nedge; i++) if (edge[i].bad) {
    dfs2(edge[i^1].to, edge[i^1].from);
  }

  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if(mark[a[i]] == 0 && f[i] == 0) {
      ans++;
    }
  }
  
  cout << ans << endl;

  return 0;
}