#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 10;
const int maxt = maxn << 2;
const int INF = 0x3f3f3f3f;
int n, q, a[maxn], Mx, sz[maxn], val[maxn];
set<int> pos[maxn];
multiset<int> vmx[maxn];
struct tnode {
  int ls, rs, mn, mxl, mxr, pl, pr, mx, lazy, sum;
  tnode() {}
  tnode(int val) {
    ls = rs = 0;
    mn = 0;
    mxl = mxr = 0;
    pl = pr = mx = 0;
    lazy = sum = 0;
  }
} t[maxt];
int rt, tcnt;
inline void pushup(int u, int l, int r) {
  int ls = t[u].ls, rs = t[u].rs;
  int mid = (l + r) >> 1;
  if (!ls && !rs) return;
  if (!rs) {
    t[u] = t[ls];
    return;
  }
  t[u].mx = max(val[mid + 1], max(t[ls].mx, t[rs].mx));
  t[u].mn = min(t[ls].mn, t[rs].mn);
  if (t[ls].mn == t[u].mn && t[rs].mn == t[u].mn) {
    t[u].pl = t[ls].pl;
    t[u].pr = t[rs].pr;
    t[u].mxl = t[ls].mxl;
    t[u].mxr = t[rs].mxr;
    int now = max(val[mid + 1], max(t[ls].mxr, t[rs].mxl));
    t[u].sum = t[ls].sum + t[rs].sum + now;
  } else {
    if (t[ls].mn == t[u].mn) {
      t[u].pl = t[ls].pl;
      t[u].pr = t[ls].pr;
      t[u].mxl = t[ls].mxl;
      t[u].mxr = max(t[ls].mxr, max(t[rs].mx, val[mid + 1]));
      t[u].sum = t[ls].sum;
    } else {
      t[u].pl = t[rs].pl;
      t[u].pr = t[rs].pr;
      t[u].mxl = max(t[rs].mxl, max(t[ls].mx, val[mid + 1]));
      t[u].mxr = t[rs].mxr;
      t[u].sum = t[rs].sum;
    }
  }
}
inline void tag(int u, int k) {
  t[u].mn += k;
  t[u].lazy += k;
}
inline void pushdown(int u) {
  int ls = t[u].ls, rs = t[u].rs;
  if (t[u].lazy != 0) {
    tag(ls, t[u].lazy);
    tag(rs, t[u].lazy);
    t[u].lazy = 0;
  }
}
void build(int &u, int l, int r) {
  u = ++tcnt;
  t[u] = tnode(0);
  if (l == r) {
    t[u].mx = 0;
    t[u].pl = t[u].pr = l;
    t[u].mn = 0;
    t[u].mxl = val[l];
    t[u].mxr = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(t[u].ls, l, mid);
  build(t[u].rs, mid + 1, r);
  pushup(u, l, r);
}
void updata1(int u, int l, int r, int p, int q, int k) {
  if (p > q) return;
  if (p <= l && r <= q) {
    tag(u, k);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(u);
  if (p <= mid) updata1(t[u].ls, l, mid, p, q, k);
  if (mid + 1 <= q) updata1(t[u].rs, mid + 1, r, p, q, k);
  pushup(u, l, r);
}
void updata2(int u, int l, int r, int p) {
  if (p < l || p > r) return;
  if (l == r) {
    t[u].mx = 0;
    t[u].mxl = val[l];
    t[u].mxr = 0;
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(u);
  if (p <= mid)
    updata2(t[u].ls, l, mid, p);
  else
    updata2(t[u].rs, mid + 1, r, p);
  pushup(u, l, r);
}
inline void prepare() {
  Mx = a[1];
  for (int i = 1; i <= n; i++) {
    pos[a[i]].insert(i);
    Mx = max(Mx, a[i]);
    sz[a[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    vmx[i].clear();
    vmx[i].insert(-INF);
  }
  for (int i = 1; i <= Mx; i++) {
    int id = *(pos[i].begin());
    vmx[id].insert(sz[i]);
  }
  for (int i = 1; i <= n; i++) {
    multiset<int>::iterator tmp = vmx[i].end();
    tmp--;
    val[i] = *tmp;
  }
  rt = tcnt = 0;
  build(rt, 0, n);
  for (int i = 1; i <= Mx; i++) {
    if (pos[i].size() <= 0) continue;
    set<int>::iterator tmp = pos[i].begin();
    int l = *tmp;
    tmp = pos[i].end();
    tmp--;
    int r = *tmp;
    updata1(rt, 0, n, l, r - 1, 1);
  }
}
inline void work(int x, int y) {
  set<int>::iterator tmp = pos[a[x]].begin();
  multiset<int>::iterator now;
  int l = *tmp;
  tmp = pos[a[x]].end();
  tmp--;
  int r = *tmp;
  now = vmx[l].find(sz[a[x]]);
  vmx[l].erase(now);
  sz[a[x]]--;
  now = vmx[l].end();
  now--;
  if (val[l] != *now) {
    val[l] = *now;
    updata2(rt, 0, n, l);
    updata2(rt, 0, n, l + 1);
  }
  pos[a[x]].erase(x);
  if (x == l || x == r) {
    updata1(rt, 0, n, l, r - 1, -1);
    tmp = pos[a[x]].begin();
    l = *tmp;
    tmp = pos[a[x]].end();
    if (pos[a[x]].size() > 0) {
      tmp--;
      r = *tmp;
      updata1(rt, 0, n, l, r - 1, 1);
    } else
      r = -1;
  }
  if (r != -1) {
    vmx[l].insert(sz[a[x]]);
    now = vmx[l].end();
    now--;
    if (val[l] != *now) {
      val[l] = *now;
      updata2(rt, 0, n, l);
      updata2(rt, 0, n, l + 1);
    }
  }
  if (sz[y] > 0) {
    tmp = pos[y].begin();
    l = *tmp;
    tmp = pos[y].end();
    tmp--;
    r = *tmp;
    now = vmx[l].find(sz[y]);
    vmx[l].erase(now);
  } else
    l = -1;
  sz[y]++;
  if (l != -1) {
    now = vmx[l].end();
    now--;
    if (val[l] != *now) {
      val[l] = *now;
      updata2(rt, 0, n, l);
      updata2(rt, 0, n, l + 1);
    }
  }
  pos[y].insert(x);
  if (x < l || x > r || l == -1) {
    if (l != -1) updata1(rt, 0, n, l, r - 1, -1);
    tmp = pos[y].begin();
    l = *tmp;
    tmp = pos[y].end();
    tmp--;
    r = *tmp;
    updata1(rt, 0, n, l, r - 1, 1);
  }
  vmx[l].insert(sz[y]);
  now = vmx[l].end();
  now--;
  if (val[l] != *now) {
    val[l] = *now;
    updata2(rt, 0, n, l);
    updata2(rt, 0, n, l + 1);
  }
  a[x] = y;
}
inline void solve() {
  int Ans = n - t[1].sum;
  printf("%d\n", Ans);
  for (int i = 1; i <= q; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    work(x, y);
    Ans = n - t[1].sum;
    printf("%d\n", Ans);
  }
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  prepare();
  solve();
  return 0;
}
