#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T &x) {
  int f = 0;
  x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
const int N = (1 << 19) + 5, lim = 2e5;
int mn[N], tag[N], L[N], R[N], A[N], sum[N];
multiset<int> T[N], s[N];
int a[N], n, Q;
void app(int o, int x) { mn[o] += x, tag[o] += x; }
void down(int o) {
  if (tag[o]) {
    app((o << 1), tag[o]);
    app((o << 1 | 1), tag[o]);
    tag[o] = 0;
  }
}
void up(int o) {
  mn[o] = min(mn[(o << 1)], mn[(o << 1 | 1)]);
  int mx = (((int)T[o].size()) ? *(--T[o].end()) : 0);
  A[o] = max(mx, max(A[(o << 1)], A[(o << 1 | 1)]));
  if (mn[(o << 1)] == mn[(o << 1 | 1)]) {
    sum[o] = sum[(o << 1)] + sum[(o << 1 | 1)];
    sum[o] += max(mx, max(R[(o << 1)], L[(o << 1 | 1)]));
    L[o] = L[(o << 1)], R[o] = R[(o << 1 | 1)];
  } else if (mn[(o << 1)] < mn[(o << 1 | 1)]) {
    sum[o] = sum[(o << 1)];
    L[o] = L[(o << 1)];
    R[o] = max(R[(o << 1)], max(mx, A[(o << 1 | 1)]));
  } else {
    sum[o] = sum[(o << 1 | 1)];
    R[o] = R[(o << 1 | 1)];
    L[o] = max(L[(o << 1 | 1)], max(mx, A[(o << 1)]));
  }
}
void upd(int o, int l, int r, int x, int y, int z) {
  if (l == x && y == r) {
    app(o, z);
    return;
  }
  down(o);
  if (x <= ((l + r) >> 1))
    upd((o << 1), l, ((l + r) >> 1), x, min(y, ((l + r) >> 1)), z);
  if (((l + r) >> 1) < y)
    upd((o << 1 | 1), ((l + r) >> 1) + 1, r, max(((l + r) >> 1) + 1, x), y, z);
  up(o);
}
void ins(int o, int l, int r, int x, int y, int z) {
  if (l == r) {
    if (z > 0)
      T[o].insert(z);
    else
      T[o].erase(T[o].find(-z));
    A[o] = L[o] = (((int)T[o].size()) >= 1);
    return;
  }
  down(o);
  if (x <= ((l + r) >> 1) && y > ((l + r) >> 1)) {
    if (z > 0)
      T[o].insert(z);
    else
      T[o].erase(T[o].find(-z));
  } else if (x <= ((l + r) >> 1))
    ins((o << 1), l, ((l + r) >> 1), x, y, z);
  else
    ins((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y, z);
  up(o);
}
void push(int i, int op) {
  if (!((int)s[i].size())) return;
  int L = *s[i].begin();
  int R = *(--s[i].end());
  if (L < R) upd(1, 1, n, L, R - 1, op);
  ins(1, 1, n, L, R, ((int)s[i].size()) * op);
}
void print() {
  int ans = L[1] + sum[1] + R[1];
  printf("%d\n", n - ans);
}
int main() {
  read(n), read(Q);
  for (int i = 1; i <= n; i++) {
    read(a[i]);
    s[a[i]].insert(i);
  }
  for (int i = 1; i <= lim; i++) push(i, 1);
  print();
  for (int i = 1; i <= Q; i++) {
    int k, x;
    read(k), read(x);
    push(a[k], -1);
    s[a[k]].erase(k);
    push(a[k], 1);
    a[k] = x;
    push(a[k], -1);
    s[a[k]].insert(k);
    push(a[k], 1);
    print();
  }
  return 0;
}
