#include <bits/stdc++.h>
using namespace std;
int a[200002], n, q;
set<int> s[200002];
int c[200002], cnt[200002];
int mn[4 * 200002], lazy[4 * 200002], mx[4 * 200002], z1, z2, md;
int maxleftl[4 * 200002], maxrightr[4 * 200002], summax[4 * 200002];
void minAgain(int x, int lo, int hi) {
  z1 = (x << 1);
  z2 = (x << 1) + 1;
  mx[x] = max(mx[z1], mx[z2]);
  md = (lo + hi) >> 1;
  mx[x] = max(mx[x], c[md]);
  if (mn[z1] < mn[z2]) {
    mn[x] = mn[z1];
    summax[x] = summax[z1];
    maxleftl[x] = maxleftl[z1];
    maxrightr[x] = max(maxrightr[z1], mx[z2]);
    maxrightr[x] = max(maxrightr[x], c[md]);
  } else if (mn[z1] > mn[z2]) {
    mn[x] = mn[z2];
    summax[x] = summax[z2];
    maxrightr[x] = maxrightr[z2];
    maxleftl[x] = max(maxleftl[z2], mx[z1]);
    maxleftl[x] = max(maxleftl[x], c[md]);
  } else {
    mn[x] = mn[z1];
    maxleftl[x] = maxleftl[z1];
    maxrightr[x] = maxrightr[z2];
    summax[x] = summax[z1] + summax[z2];
    int val = max(maxrightr[2 * x], maxleftl[2 * x + 1]);
    summax[x] += max(val, c[md]);
  }
}
void Build(int x, int lo, int hi) {
  if (lo == hi) {
    return;
  }
  int mid = (lo + hi) >> 1;
  Build((x << 1), lo, mid);
  Build((x << 1) + 1, mid + 1, hi);
  minAgain(x, lo, hi);
}
void Down(int x) {
  if (lazy[x] == 0) return;
  mn[(x << 1)] += lazy[x];
  mn[(x << 1) + 1] += lazy[x];
  lazy[(x << 1)] += lazy[x];
  lazy[(x << 1) + 1] += lazy[x];
  lazy[x] = 0;
}
void Upd(int x, int lo, int hi, int st, int en, int val) {
  if (lo > en || hi < st) return;
  if (st <= lo && hi <= en) {
    mn[x] += val;
    lazy[x] += val;
    return;
  }
  int mid = (lo + hi) >> 1;
  Down(x);
  Upd((x << 1), lo, mid, st, en, val);
  Upd((x << 1) + 1, mid + 1, hi, st, en, val);
  minAgain(x, lo, hi);
}
int qpos;
void Wow(int x, int lo, int hi) {
  int mid = (lo + hi) / 2;
  Down(x);
  if (mid == qpos) {
    minAgain(x, lo, hi);
    return;
  }
  if (mid > qpos)
    Wow(2 * x, lo, mid);
  else
    Wow(2 * x + 1, mid + 1, hi);
  minAgain(x, lo, hi);
}
void Change(int pos) {
  qpos = pos;
  Wow(1, 1, n + 1);
}
void scam(int x, int val) {
  int j = *s[x].begin(), k = *s[x].rbegin();
  if (j < k) Upd(1, 1, n + 1, j + 1, k, val);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  scanf("%ld %ld", &n, &q);
  int i, j, k;
  for (i = 1; i <= n; i++) {
    scanf("%ld", &a[i]);
    s[a[i]].insert(i);
    ++cnt[a[i]];
  }
  for (i = 1; i < 200002; ++i) {
    if (cnt[i]) {
      j = *s[i].begin();
      c[j] = cnt[i];
    }
  }
  Build(1, 1, n + 1);
  for (i = 1; i < 200002; ++i) {
    if (cnt[i] > 1) {
      j = *s[i].begin();
      k = *s[i].rbegin();
      if (j < k) Upd(1, 1, n + 1, j + 1, k, 1);
    }
  }
  printf("%ld\n", n - summax[1]);
  int poss, val1, val2;
  int d1, d2, d3, d4;
  for (i = 1; i <= q; ++i) {
    scanf("%ld %ld", &poss, &val1);
    val2 = a[poss];
    ++cnt[val1];
    --cnt[val2];
    a[poss] = val1;
    int wat = *s[val2].begin();
    c[wat] = 0;
    Change(wat);
    d1 = wat + 1;
    d2 = *s[val2].rbegin();
    s[val2].erase(s[val2].find(poss));
    if (!s[val2].empty()) {
      wat = *s[val2].begin();
      c[wat] = cnt[val2];
      Change(wat);
      d3 = wat + 1;
      d4 = *s[val2].rbegin();
      if (d1 < d3)
        Upd(1, 1, n + 1, d1, d3 - 1, -1);
      else if (d4 < d2)
        Upd(1, 1, n + 1, d4 + 1, d2, -1);
    } else
      Upd(1, 1, n + 1, d1, d2, -1);
    if (!s[val1].empty()) {
      wat = *s[val1].begin();
      c[wat] = 0;
      Change(wat);
      d1 = wat + 1;
      d2 = *s[val1].rbegin();
    } else
      d1 = -1;
    s[val1].insert(poss);
    wat = *s[val1].begin();
    c[wat] = cnt[val1];
    Change(wat);
    d3 = wat + 1;
    d4 = *s[val1].rbegin();
    if (d1 == -1)
      Upd(1, 1, n + 1, d3, d4, 1);
    else {
      if (d3 < d1)
        Upd(1, 1, n + 1, d3, d1 - 1, 1);
      else if (d4 > d2)
        Upd(1, 1, n + 1, d2 + 1, d4, 1);
    }
    printf("%ld\n", n - summax[1]);
  }
}
