#include <bits/stdc++.h>
using namespace std;
int n, m;
int p[200005];
int head[200005];
vector<int> G[200005];
int tot[200005];
int vis[200005], cnt = 0;
int find(int u) {
  if (p[u] != u)
    return p[u] = find(p[u]);
  else
    return u;
}
void print() { printf("%d\n", n - cnt - 1); }
void dfs(int u) {
  if (u <= n - 1 && vis[u] == 0 && find(u) == find(u + 1)) vis[u] = 1, cnt++;
  if (u >= 2 && vis[u - 1] == 0 && find(u - 1) == find(u))
    vis[u - 1] = 1, cnt++;
  for (int i = 0; i < G[u].size(); i++)
    if (G[u][i] != u) dfs(G[u][i]);
}
int main() {
  cin >> n >> m;
  int t;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &t);
    if (head[t] == 0)
      head[t] = p[i] = i;
    else
      p[i] = head[t];
    G[head[t]].push_back(i);
    tot[head[t]]++;
  }
  for (int i = 1; i <= n - 1; i++)
    if (p[i] == p[i + 1]) vis[i] = 1, cnt++;
  print();
  int a, b;
  for (int i = 1; i <= m - 1; i++) {
    scanf("%d%d", &a, &b);
    p[head[b]] = head[a];
    if (tot[head[b]] > tot[head[a]])
      dfs(head[a]);
    else
      dfs(head[b]);
    G[head[a]].push_back(head[b]);
    tot[head[a]] += tot[head[b]];
    print();
  }
  return 0;
}
