#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const double pi = 3.1415926535897932, eps = 1e-6;
void chmax(pair<int, long long> &x, pair<int, long long> y) {
  if (x < y) x = y;
}
void chmin(int &x, int y) {
  if (x > y) x = y;
}
int n, m, C[200005], v[200005], sumv, siz[200005];
int fa[200005], pos[200005];
vector<int> ve[200005];
int find(int x) {
  if (x == fa[x]) return x;
  return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
  int xx = find(x), yy = find(y);
  if (siz[xx] > siz[yy]) swap(xx, yy);
  v[yy] += v[xx];
  siz[yy] += siz[xx];
  for (int(i) = (0); (i) < (siz[xx]); (i)++) {
    int u = ve[xx][i];
    if (u > 1 && find(u - 1) == yy) v[yy]++, sumv++;
    if (u < n && find(u + 1) == yy) v[yy]++, sumv++;
  }
  while (ve[xx].size()) ve[yy].push_back(ve[xx].back()), ve[xx].pop_back();
  fa[xx] = fa[yy];
  siz[xx] = 0;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = (1); (i) <= (n); (i)++)
    fa[i] = i, ve[i].push_back(i), siz[i] = 1;
  for (int(i) = (1); (i) <= (n); (i)++) {
    scanf("%d", C + i);
    if (pos[C[i]]) unite(pos[C[i]], i);
    pos[C[i]] = i;
  }
  printf("%d\n", n - sumv - 1);
  for (int(i) = (1); (i) < (m); (i)++) {
    int x, y;
    scanf("%d%d", &x, &y);
    unite(pos[x], pos[y]);
    printf("%d\n", n - sumv - 1);
  }
  return 0;
}
