#include <bits/stdc++.h>
using namespace std;
int n, m, p[200005], val[200005], ans, ind[200005];
vector<int> v[200005];
int find(int x) {
  if (x == p[x]) return x;
  return p[x] = find(p[x]);
}
void join(int x, int y) {
  x = find(x);
  y = find(y);
  if ((int)v[x].size() < (int)v[y].size()) swap(x, y);
  val[x] += val[y];
  p[y] = x;
  for (int i = 0; i < v[y].size(); i++) {
    if (ind[v[y][i] + 1] == x) {
      val[x]++;
      ans--;
    }
    if (ind[v[y][i] - 1] == x) {
      val[x]++;
      ans--;
    }
  }
  for (int i = 0; i < v[y].size(); i++) {
    ind[v[y][i]] = x;
    v[x].push_back(v[y][i]);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    p[i] = i;
  }
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    ind[i] = x;
    v[x].push_back(i);
  }
  ans = n - 1;
  for (int i = 1; i <= m; i++)
    for (int j = 1; j < v[i].size(); j++)
      if (v[i][j - 1] + 1 == v[i][j]) {
        val[i]++;
        ans--;
      }
  cout << ans << '\n';
  m--;
  while (m--) {
    int x, y;
    cin >> x >> y;
    join(x, y);
    cout << ans << '\n';
  }
  return 0;
}
