#include <bits/stdc++.h>
const int N = 200000 + 47;
const int T = N << 2 | 47;
const int INF = 0x3f3f3f3f;
int a[N], n, m;
std::set<int> set[N];
int max[T], cov[T], lmax[T], rmax[T], add[T], sum[T];
void input(int &x) {
  char c;
  for (c = getchar(); !isdigit(c); c = getchar())
    ;
  for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
}
void update(int rt) {
  max[rt] = std::max(max[rt << 1], max[rt << 1 | 1]);
  cov[rt] = (cov[rt << 1] && cov[rt << 1 | 1]) || add[rt];
  if (cov[rt])
    sum[rt] = lmax[rt] = rmax[rt] = max[rt];
  else {
    if (!cov[rt << 1])
      lmax[rt] = lmax[rt << 1];
    else
      lmax[rt] = std::max(max[rt << 1], lmax[rt << 1 | 1]);
    if (!cov[rt << 1 | 1])
      rmax[rt] = rmax[rt << 1 | 1];
    else
      rmax[rt] = std::max(max[rt << 1 | 1], rmax[rt << 1]);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1] -
              std::min(rmax[rt << 1], lmax[rt << 1 | 1]);
  }
}
void ins(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    ++add[rt], cov[rt] = 1;
    lmax[rt] = rmax[rt] = sum[rt] = max[rt];
    return;
  }
  int mid = l + r >> 1;
  if (L <= mid) ins(rt << 1, l, mid, L, R);
  if (R > mid) ins(rt << 1 | 1, mid + 1, r, L, R);
  update(rt);
}
void dec(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    --add[rt], cov[rt] = add[rt] > 0;
    if (l != r)
      update(rt);
    else if (cov[rt])
      lmax[rt] = rmax[rt] = sum[rt] = max[rt];
    else
      lmax[rt] = rmax[rt] = 0, sum[rt] = max[rt];
    return;
  }
  int mid = l + r >> 1;
  if (L <= mid) dec(rt << 1, l, mid, L, R);
  if (R > mid) dec(rt << 1 | 1, mid + 1, r, L, R);
  update(rt);
}
void modify(int rt, int l, int r, int p, int x) {
  if (l == r) {
    max[rt] += x, sum[rt] = max[rt];
    if (cov[rt])
      lmax[rt] = rmax[rt] = max[rt];
    else
      lmax[rt] = rmax[rt] = 0;
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid)
    modify(rt << 1, l, mid, p, x);
  else
    modify(rt << 1 | 1, mid + 1, r, p, x);
  update(rt);
}
int main() {
  int x, y, z, l, r;
  input(n), input(m);
  for (int i = 1; i <= n; ++i) input(a[i]);
  for (int i = 1; i <= n; ++i) set[a[i]].insert(i);
  for (int i = 1; i <= n; ++i)
    if (*set[a[i]].begin() == i) {
      modify(1, 1, n, i, set[a[i]].size());
      if (set[a[i]].size() != 1) ins(1, 1, n, i, *set[a[i]].rbegin() - 1);
    }
  printf("%d\n", n - sum[1]);
  while (m--) {
    input(x), input(y);
    if (set[a[x]].size() != 1) {
      l = *set[a[x]].begin();
      r = *set[a[x]].rbegin();
      if (l == x) {
        dec(1, 1, n, l, r - 1);
        if (set[a[x]].size() > 2) ins(1, 1, n, *++set[a[x]].begin(), r - 1);
        z = set[a[x]].size();
        modify(1, 1, n, l, -z);
        modify(1, 1, n, *++set[a[x]].begin(), z - 1);
      } else if (r == x) {
        dec(1, 1, n, l, r - 1);
        if (set[a[x]].size() > 2) ins(1, 1, n, l, *++set[a[x]].rbegin() - 1);
        modify(1, 1, n, l, -1);
      } else
        modify(1, 1, n, l, -1);
      set[a[x]].erase(set[a[x]].find(x));
    } else {
      modify(1, 1, n, x, -1);
      set[a[x]].erase(set[a[x]].begin());
    }
    if (set[y].empty())
      modify(1, 1, n, x, 1);
    else {
      l = *set[y].begin();
      r = *set[y].rbegin();
      if (x < l) {
        if (set[y].size() != 1) dec(1, 1, n, l, r - 1);
        ins(1, 1, n, x, r - 1);
        z = set[y].size();
        modify(1, 1, n, l, -z);
        modify(1, 1, n, x, z + 1);
      } else if (x > r) {
        if (set[y].size() != 1) dec(1, 1, n, l, r - 1);
        ins(1, 1, n, l, x - 1);
        modify(1, 1, n, l, 1);
      } else
        modify(1, 1, n, l, 1);
    }
    a[x] = y;
    set[y].insert(x);
    printf("%d\n", n - sum[1]);
  }
  return 0;
}
