#include <bits/stdc++.h>
using namespace std;
int n, Q, a[200100], m, opt, x, y;
set<int> S[200100];
struct Tree {
  int l, r, Lmax, L, Rmax, R, tag, val, S, Max;
} tree[1000100];
void pushdown(int x) {
  tree[x * 2].val += tree[x].tag;
  tree[x * 2 + 1].val += tree[x].tag;
  tree[x * 2].tag += tree[x].tag;
  tree[x * 2 + 1].tag += tree[x].tag;
  tree[x].tag = 0;
}
void pushup(int x) {
  tree[x].val = min(tree[x * 2].val, tree[x * 2 + 1].val);
  tree[x].Max = max(tree[x * 2].Max, tree[x * 2 + 1].Max);
  if (tree[x * 2].val == tree[x].val && tree[x * 2 + 1].val == tree[x].val) {
    tree[x].R = tree[x * 2 + 1].R;
    tree[x].L = tree[x * 2].L;
    tree[x].Lmax = tree[x * 2].Lmax;
    tree[x].Rmax = tree[x * 2 + 1].Rmax;
    tree[x].S = tree[x * 2].S + tree[x * 2 + 1].S +
                max(tree[x * 2].Rmax, tree[x * 2 + 1].Lmax);
  } else if (tree[x * 2].val == tree[x].val) {
    tree[x].R = tree[x * 2].R;
    tree[x].L = tree[x * 2].L;
    tree[x].Lmax = tree[x * 2].Lmax;
    tree[x].Rmax = max(tree[x * 2].Rmax, tree[x * 2 + 1].Max);
    tree[x].S = tree[x * 2].S;
  } else if (tree[x * 2 + 1].val == tree[x].val) {
    tree[x].R = tree[x * 2 + 1].R;
    tree[x].L = tree[x * 2 + 1].L;
    tree[x].Rmax = tree[x * 2 + 1].Rmax;
    tree[x].Lmax = max(tree[x * 2].Max, tree[x * 2 + 1].Lmax);
    tree[x].S = tree[x * 2 + 1].S;
  }
}
void build(int x, int l, int r) {
  tree[x].l = l;
  tree[x].r = r;
  if (l == r) {
    tree[x].L = tree[x].R = l;
    return;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  pushup(x);
}
void insert(int x, int l, int r, int z) {
  if (tree[x].l > r || l > tree[x].r) return;
  if (tree[x].l >= l && tree[x].r <= r) {
    tree[x].val += z;
    tree[x].tag += z;
    return;
  }
  pushdown(x);
  insert(x * 2, l, r, z);
  insert(x * 2 + 1, l, r, z);
  pushup(x);
}
void insert2(int x, int y, int z) {
  if (tree[x].l == tree[x].r) {
    tree[x].Lmax = z;
    tree[x].Max = z;
    return;
  }
  pushdown(x);
  int mid = (tree[x].l + tree[x].r) / 2;
  if (y <= mid)
    insert2(x * 2, y, z);
  else
    insert2(x * 2 + 1, y, z);
  pushup(x);
}
void change(int x, int y) {
  if (!S[x].size()) return;
  insert(1, *S[x].begin(), *S[x].rbegin() - 1, y);
  if (y == -1)
    insert2(1, *S[x].begin(), 0);
  else
    insert2(1, *S[x].begin(), S[x].size());
}
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", n - tree[1].S - tree[1].Lmax);
  while (Q--) {
    scanf("%d%d", &x, &y);
    change(a[x], -1);
    change(y, -1);
    int lst = a[x];
    S[a[x]].erase(x);
    a[x] = y;
    S[a[x]].insert(x);
    change(lst, 1);
    change(y, 1);
    printf("%d\n", n - tree[1].S - tree[1].Lmax);
  }
}
