#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, Q, a[N], m, opt, x, y;
set<int> S[N];
struct Tree {
  int l, r, Lmax, L, Rmax, R, flag, num, S, Max;
} T[N * 4];
void down(int x) {
  T[x * 2].num += T[x].flag;
  T[x * 2 + 1].num += T[x].flag;
  T[x * 2].flag += T[x].flag;
  T[x * 2 + 1].flag += T[x].flag;
  T[x].flag = 0;
}
void update(int x) {
  T[x].num = min(T[x * 2].num, T[x * 2 + 1].num);
  T[x].Max = max(T[x * 2].Max, T[x * 2 + 1].Max);
  if (T[x * 2].num == T[x].num && T[x * 2 + 1].num == T[x].num) {
    T[x].R = T[x * 2 + 1].R;
    T[x].L = T[x * 2].L;
    T[x].Lmax = T[x * 2].Lmax;
    T[x].Rmax = T[x * 2 + 1].Rmax;
    T[x].S =
        T[x * 2].S + T[x * 2 + 1].S + max(T[x * 2].Rmax, T[x * 2 + 1].Lmax);
  } else if (T[x * 2].num == T[x].num) {
    T[x].R = T[x * 2].R;
    T[x].L = T[x * 2].L;
    T[x].Lmax = T[x * 2].Lmax;
    T[x].Rmax = max(T[x * 2].Rmax, T[x * 2 + 1].Max);
    T[x].S = T[x * 2].S;
  } else if (T[x * 2 + 1].num == T[x].num) {
    T[x].R = T[x * 2 + 1].R;
    T[x].L = T[x * 2 + 1].L;
    T[x].Rmax = T[x * 2 + 1].Rmax;
    T[x].Lmax = max(T[x * 2].Max, T[x * 2 + 1].Lmax);
    T[x].S = T[x * 2 + 1].S;
  }
}
void build(int x, int l, int r) {
  T[x].l = l;
  T[x].r = r;
  if (l == r) {
    T[x].L = T[x].R = l;
    return;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  update(x);
}
void insert(int x, int l, int r, int z) {
  if (T[x].l > r || l > T[x].r) return;
  if (T[x].l >= l && T[x].r <= r) {
    T[x].num += z;
    T[x].flag += z;
    return;
  }
  down(x);
  insert(x * 2, l, r, z);
  insert(x * 2 + 1, l, r, z);
  update(x);
}
void insert2(int x, int y, int z) {
  if (T[x].l == T[x].r) {
    T[x].Lmax = z;
    T[x].Max = z;
    return;
  }
  down(x);
  int mid = (T[x].l + T[x].r) / 2;
  if (y <= mid)
    insert2(x * 2, y, z);
  else
    insert2(x * 2 + 1, y, z);
  update(x);
}
void change(int x, int y) {
  if (!S[x].size()) return;
  set<int>::iterator iter = S[x].begin(), iter2 = S[x].end();
  iter2--;
  insert(1, *iter, *iter2 - 1, y);
  if (y == -1)
    insert2(1, *iter, 0);
  else
    insert2(1, *iter, S[x].size());
}
int calc() { return n - T[1].S - T[1].Lmax; }
int main() {
  scanf("%d%d", &n, &Q);
  m = 200000;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), S[a[i]].insert(i);
  build(1, 1, n);
  for (int i = 1; i <= m; i++)
    if (!S[i].empty()) change(i, 1);
  printf("%d\n", calc());
  while (Q--) {
    scanf("%d%d", &x, &y);
    change(a[x], -1);
    change(y, -1);
    int last = a[x];
    S[a[x]].erase(x);
    a[x] = y;
    S[a[x]].insert(x);
    change(last, 1);
    change(y, 1);
    printf("%d\n", calc());
  }
}
