#include <bits/stdc++.h>
const int N = 200005;
int n, q, a[N], val[N];
struct data {
  int a[5];
} info[N << 2];
int tag[N << 2];
std::set<int> s[N];
void setadd(int x, int v) { tag[x] += v, info[x].a[0] += v; }
void pushdown(int x) {
  if (tag[x]) setadd(x << 1, tag[x]), setadd(x << 1 | 1, tag[x]), tag[x] = 0;
}
void up(int &x, int y) { x = std::max(x, y); }
void pushup(int x) {
  data L = info[x << 1], R = info[x << 1 | 1];
  if (L.a[0] < R.a[0]) {
    up(L.a[3], std::max(std::max(R.a[2], R.a[3]), R.a[4]));
    info[x] = L;
  } else if (L.a[0] > R.a[0]) {
    up(R.a[2], std::max(std::max(L.a[2], L.a[3]), L.a[4]));
    info[x] = R;
  } else {
    info[x].a[0] = L.a[0];
    info[x].a[1] = L.a[1] + R.a[1] + std::max(L.a[3], R.a[2]);
    info[x].a[2] = L.a[2];
    info[x].a[3] = R.a[3];
    info[x].a[4] = std::max(std::max(L.a[4], R.a[4]), std::max(L.a[3], R.a[2]));
  }
}
void modify(int L, int R, int v, int o = 1, int l = 1, int r = n) {
  if (L <= l && R >= r) return setadd(o, v);
  int mid = l + r >> 1;
  pushdown(o);
  if (L <= mid) modify(L, R, v, o << 1, l, mid);
  if (R > mid) modify(L, R, v, o << 1 | 1, mid + 1, r);
  pushup(o);
}
void modify_v(int pos, int o = 1, int l = 1, int r = n) {
  if (l == r) {
    info[o].a[2] = val[l];
    return;
  }
  int mid = l + r >> 1;
  pushdown(o);
  if (pos <= mid)
    modify_v(pos, o << 1, l, mid);
  else
    modify_v(pos, o << 1 | 1, mid + 1, r);
  pushup(o);
}
void insert(int x, int y) {
  if (s[y].size() > 1) modify(*s[y].begin(), *s[y].rbegin() - 1, -1);
  if (s[y].size()) val[*s[y].begin()] = 0, modify_v(*s[y].begin());
  s[y].insert(x);
  val[*s[y].begin()] = s[y].size(), modify_v(*s[y].begin());
  if (s[y].size() > 1) modify(*s[y].begin(), *s[y].rbegin() - 1, 1);
}
void remove(int x, int y) {
  if (s[y].size() > 1) modify(*s[y].begin(), *s[y].rbegin() - 1, -1);
  val[*s[y].begin()] = 0, modify_v(*s[y].begin());
  s[y].erase(x);
  if (s[y].size()) val[*s[y].begin()] = s[y].size(), modify_v(*s[y].begin());
  if (s[y].size() > 1) modify(*s[y].begin(), *s[y].rbegin() - 1, 1);
}
int query() { return n - info[1].a[1] - info[1].a[2] - info[1].a[3]; }
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i], insert(i, a[i]);
  std::cout << query() << '\n';
  for (int i = 1; i <= q; ++i) {
    int x, y;
    std::cin >> x >> y;
    remove(x, a[x]), insert(x, a[x] = y);
    std::cout << query() << '\n';
  }
  return 0;
}
