#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int ans = 0;
template <typename T>
struct BIT {
  int N;
  vector<T> bit;
  void init(int n) {
    N = n;
    bit.assign(n + 1, 0);
  }
  void update(int idx, T val) {
    while (idx <= N) {
      bit[idx] += val;
      idx += idx & -idx;
    }
  }
  T pref(int idx) {
    T ans = 0;
    while (idx > 0) {
      ans += bit[idx];
      idx -= idx & -idx;
    }
    return ans;
  }
  T query(int l, int r) { return pref(r) - pref(l - 1); }
};
vector<int> v[N];
struct DSU {
  int par[N];
  int sz[N];
  int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
  void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
  }
  void init(int n) {
    for (int i = 0; i <= n; i++) par[i] = i, sz[i] = v[i].size();
  }
};
DSU d;
int32_t main() {
  4;
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  set<int> s[n];
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    v[x].push_back(i + 1);
    s[x].insert(i + 1);
  }
  int sum = 0;
  BIT<int> b;
  b.init(n);
  vector<int> ans(n);
  for (int i = 0; i < n; i++) {
    if (v[i].empty()) continue;
    int cnt = 0;
    sort(v[i].begin(), v[i].end());
    for (int j = 1; j < v[i].size(); j++) {
      if (v[i][j] != v[i][j - 1] + 1) cnt++;
    }
    ans[i] = cnt + 1;
    b.update(i + 1, cnt + 1);
    sum += (cnt + 1);
  }
  sum--;
  cout << sum << "\n";
  d.init(n);
  m--;
  while (m--) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    x = d.find(x);
    y = d.find(y);
    if (x == y) {
      cout << 0 << "\n";
      continue;
    }
    if (s[x].size() < s[y].size()) swap(x, y);
    b.update(y + 1, -ans[y]);
    ans[y] = 0;
    for (int e : s[y]) {
      if (s[x].count(e + 1) == 0 and s[x].count(e - 1) == 0) {
        ans[x]++;
        b.update(x + 1, 1);
      } else if (s[x].count(e + 1) and s[x].count(e - 1)) {
        ans[x]--;
        b.update(x + 1, -1);
      }
      s[x].insert(e);
    }
    d.merge(x, y);
    cout << b.query(1, n) - 1 << "\n";
  }
}
