#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int arr[MAXN + 5];
struct segtree {
  struct node {
    int l, r;
    int tg, cmn;
    int lmx, rmx, mx, ans, cnt;
  } t[4 * MAXN + 5];
  void pushup(int x) {
    t[x].mx = max(t[(x << 1)].mx, t[(x << 1 | 1)].mx);
    t[x].cmn = min(t[(x << 1)].cmn, t[(x << 1 | 1)].cmn);
    if (t[x].cmn == t[(x << 1)].cmn)
      t[x].lmx = t[(x << 1)].lmx;
    else
      t[x].lmx = max(t[(x << 1)].mx, t[(x << 1 | 1)].lmx);
    if (t[x].cmn == t[(x << 1 | 1)].cmn)
      t[x].rmx = t[(x << 1 | 1)].rmx;
    else
      t[x].rmx = max(t[(x << 1 | 1)].mx, t[(x << 1)].rmx);
    if (t[x].cmn != t[(x << 1 | 1)].cmn) {
      t[x].ans = t[(x << 1)].ans;
      t[x].cnt = t[(x << 1)].cnt + t[(x << 1 | 1)].r - t[(x << 1 | 1)].l + 1;
    } else if (t[x].cmn != t[(x << 1)].cmn) {
      t[x].ans = t[(x << 1 | 1)].ans;
      t[x].cnt = t[(x << 1 | 1)].cnt + t[(x << 1)].r - t[(x << 1)].l + 1;
    } else {
      t[x].ans = t[(x << 1)].ans + t[(x << 1 | 1)].ans;
      t[x].cnt = t[(x << 1)].cnt + t[(x << 1 | 1)].cnt;
      if (t[(x << 1)].rmx != -1 || t[(x << 1 | 1)].lmx != -1)
        t[x].ans += max(t[(x << 1)].rmx, t[(x << 1 | 1)].lmx), t[x].cnt++;
    }
  }
  void pushdown(int x) {
    if (t[x].tg) {
      t[(x << 1)].tg += t[x].tg, t[(x << 1 | 1)].tg += t[x].tg;
      t[(x << 1)].cmn += t[x].tg, t[(x << 1 | 1)].cmn += t[x].tg;
      t[x].tg = 0;
    }
  }
  void build(int x, int l, int r) {
    t[x].l = l, t[x].r = r, t[x].tg = 0, t[x].ans = 0;
    if (l == r) {
      t[x].cmn = 0, t[x].lmx = t[x].rmx = -1, t[x].mx = max(arr[l], arr[l + 1]);
      return;
    }
    int mid = (l + r) >> 1;
    build((x << 1), l, mid), build((x << 1 | 1), mid + 1, r);
    pushup(x);
  }
  void update(int x, int p) {
    if (t[x].l > p || t[x].r < p) return;
    if (t[x].l == t[x].r) {
      t[x].mx = max(arr[p], arr[p + 1]);
      return;
    }
    pushdown(x);
    update((x << 1), p);
    update((x << 1 | 1), p);
    pushup(x);
  }
  void modify(int x, int l, int r, int d) {
    if (l <= t[x].l && t[x].r <= r) {
      t[x].tg += d, t[x].cmn += d;
      return;
    }
    if (l > t[x].r || r < t[x].l) return;
    pushdown(x);
    modify((x << 1), l, r, d);
    modify((x << 1 | 1), l, r, d);
    pushup(x);
  }
} T;
set<int> st[MAXN + 5];
int a[MAXN + 5], n, q;
void update(int p) { T.update(1, p - 1), T.update(1, p); }
void remove(int x) {
  int l = *st[a[x]].begin(), r = *st[a[x]].rbegin();
  T.modify(1, l, r - 1, -1), arr[l] = 0, update(l);
  st[a[x]].erase(x);
  if (!st[a[x]].empty()) {
    int l = *st[a[x]].begin(), r = *st[a[x]].rbegin();
    T.modify(1, l, r - 1, 1), arr[l] = st[a[x]].size(), update(l);
  }
}
void add(int x) {
  if (!st[a[x]].empty()) {
    int l = *st[a[x]].begin(), r = *st[a[x]].rbegin();
    T.modify(1, l, r - 1, -1), arr[l] = 0, update(l);
  }
  st[a[x]].insert(x);
  int l = *st[a[x]].begin(), r = *st[a[x]].rbegin();
  T.modify(1, l, r - 1, 1), arr[l] = st[a[x]].size(), update(l);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  T.build(1, 0, n);
  for (int i = 1; i <= n; i++) add(i);
  printf("%d\n", T.t[1].cnt - T.t[1].ans);
  for (int i = 1; i <= q; i++) {
    int it, xt;
    scanf("%d%d", &it, &xt);
    remove(it), a[it] = xt, add(it);
    printf("%d\n", T.t[1].cnt - T.t[1].ans);
  }
}
