#include <bits/stdc++.h>
using namespace std;
struct node {
  int l, r, mx, mn, tag, sum;
  node operator+(const node &b) const {
    node tmp;
    tmp.tag = 0, tmp.mx = max(mx, b.mx), tmp.mn = min(mn, b.mn);
    if (mn < b.mn) {
      tmp.l = l, tmp.r = max(r, b.mx), tmp.sum = sum;
    } else if (mn > b.mn) {
      tmp.r = b.r, tmp.l = max(mx, b.l), tmp.sum = b.sum;
    } else {
      tmp.l = l, tmp.r = b.r, tmp.sum = sum + b.sum + max(r, b.l);
    }
    return tmp;
  }
} tr[1600010];
int n, m, a[200010];
set<int> col[200010];
void add(int t, int c) {
  tr[t].tag += c;
  tr[t].mn += c;
}
void pushdown(int t) {
  add(t << 1, tr[t].tag);
  add(t << 1 | 1, tr[t].tag);
  tr[t].tag = 0;
}
void add(int ll, int rr, int l, int r, int t, int c) {
  if (ll <= l && r <= rr) return add(t, c);
  int mid = (l + r) >> 1;
  pushdown(t);
  if (ll <= mid) add(ll, rr, l, mid, t << 1, c);
  if (mid < rr) add(ll, rr, mid + 1, r, t << 1 | 1, c);
  tr[t] = tr[t << 1] + tr[t << 1 | 1];
}
void cg(int a, int l, int r, int t, int c) {
  if (l == r) return tr[t].l = tr[t].r = tr[t].mx = c, void();
  int mid = (l + r) >> 1;
  pushdown(t);
  if (a <= mid)
    cg(a, l, mid, t << 1, c);
  else
    cg(a, mid + 1, r, t << 1 | 1, c);
  tr[t] = tr[t << 1] + tr[t << 1 | 1];
}
int qry() { return n - tr[1].sum; }
void cg(int c, int w) {
  if (!col[c].empty()) {
    if (col[c].size() > 1)
      add(*col[c].begin(), (*col[c].rbegin()) - 1, 0, n, 1, w);
    cg(*col[c].begin(), 0, n, 1, (w < 0) ? 0 : col[c].size());
  }
}
void work(int x, int c) {
  int ty = c > 0;
  c = abs(c);
  cg(c, -1);
  if (ty)
    col[c].insert(x);
  else
    col[c].erase(x);
  cg(c, 1);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), work(i, a[i]);
  printf("%d\n", qry());
  int x, y;
  while (m--) {
    scanf("%d%d", &x, &y);
    work(x, -a[x]);
    work(x, a[x] = y);
    printf("%d\n", qry());
  }
}
