#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ld = long double;
using pii = pair<int, int>;
struct DSU {
  int n;
  vi p;
  vector<map<int, int>> rng;
  int num;
  DSU(int n, vector<vi> &pos) : n(n), p(n, -1), rng(n) {
    num = 0;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < pos[i].size(); j++) {
        if (j > 0 && pos[i][j - 1] + 1 == pos[i][j])
          rng[i].rbegin()->second = pos[i][j];
        else
          rng[i][pos[i][j]] = pos[i][j];
      }
    for (int i = 0; i < n; i++) num += rng[i].size();
  }
  int find(int i) { return p[i] < 0 ? i : (p[i] = find(p[i])); }
  void join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (rng[b].size() > rng[a].size()) swap(a, b);
    num -= rng[b].size();
    for (auto &it : rng[b]) {
      int x = it.first, y = it.second;
      auto o = rng[a].lower_bound(x);
      if (o != rng[a].end() && y + 1 == o->first) {
        y = o->second, rng[a].erase(o), num--;
        o = rng[a].lower_bound(x);
      }
      if (o != rng[a].begin()) {
        o = prev(o);
        if (o->second + 1 == x) x = o->first, rng[a].erase(o), num--;
      }
      rng[a][x] = y;
      num++;
    }
    p[b] = a;
  }
};
void solve() {
  int n, m;
  cin >> n >> m;
  vi a(n);
  for (int i = 0; i < n; i++) cin >> a[i], a[i]--;
  vector<vi> pos(m);
  for (int i = 0; i < n; i++) pos[a[i]].push_back(i);
  DSU dsu(m, pos);
  cout << dsu.num - 1 << '\n';
  for (int i = 0; i < m - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    dsu.join(x, y);
    cout << dsu.num - 1 << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}
