#include <bits/stdc++.h>
#pragma GCC optimize "-O3"
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
int a[200200], b[200200];
pair<int, int> p[200200];
set<int> s[200200];
int vst[200200];
int id[200200], R[200200], val[200200];
int q[200200];
int fir[200200], last[200200];
int mxx[200200][18];
int cnt[200200];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i), s[a[i]].insert(i);
    cnt[a[i]]++;
    if (!fir[a[i]]) fir[a[i]] = i;
    last[a[i]] = i;
  }
  for (int i = 0; i < m; i++) scanf("%d %d", &p[i].first, &p[i].second);
  int M = 900, runs = 0, ok = 0;
  if (m == 0) p[m++] = pair<int, int>(1, a[1]), ok = 1;
  for (int i = 0; i < m; i += M) {
    int ed = min(m, i + M);
    for (int j = 1; j <= n; j++) b[j] = a[j];
    runs++;
    register int nn = 0;
    for (int j = i; j < ed; j++) {
      vst[b[p[j].first]] = runs;
      q[nn++] = b[p[j].first];
      vst[b[p[j].first] = p[j].second] = runs;
      q[nn++] = p[j].second;
    }
    int cur = 0, pre = 0, now = 0, mx = 0, pregood = 0, good;
    for (int i = 1, j = 1; i <= n; i = j, pregood = pre) {
      if (vst[a[i]] == runs) {
        id[i] = -cur - 1;
        j++;
        continue;
      }
      mx = 0, now = i, cur++;
      good = 1;
      while (j <= now) {
        id[j] = cur;
        if (vst[a[j]] != runs) {
          mx = max(mx, cnt[a[j]]);
          now = max(now, last[a[j]]);
        } else
          good = 0;
        j++;
      }
      if (pregood && good) {
        cur--;
        val[cur] = max(val[cur], mx);
        for (int k = R[cur] + 1; k <= now; k++) id[k] = cur;
        R[cur] = now;
        continue;
      }
      val[cur] = mx;
      R[cur] = now;
    }
    for (int i = 1; i <= cur; i++) mxx[i][0] = val[i];
    int L = 31 - __builtin_clz(cur);
    for (int j = 1; j <= L; j++) {
      for (int i = 1; i <= cur; i++) {
        mxx[i][j] = max(mxx[i][j - 1], mxx[min(i + (1 << j - 1), cur)][j - 1]);
      }
    }
    for (int i = 1; i <= cur; i++) val[i] += val[i - 1];
    sort(q, q + nn);
    nn = unique(q, q + nn) - q;
    sort(q, q + nn, [&](int a, int b) { return fir[a] < fir[b]; });
    if (i == 0) {
      int sum = 0;
      int pre = 0;
      for (register int i = 0, j = 0; i < nn; i = j) {
        if (fir[q[i]] == 0) {
          j++;
          continue;
        }
        int now = last[q[i]], mx = 0;
        while (1) {
          while (j < nn && now >= fir[q[j]])
            now = max(now, last[q[j]]), mx = max(mx, cnt[q[j]]), j++;
          if (id[now] < 0 || now == R[id[now]]) break;
          now = R[id[now]];
        }
        int st = id[fir[q[i]]] < 0 ? -id[fir[q[i]]] : id[fir[q[i]]];
        int edd = id[now] < 0 ? -id[now] - 1 : id[now];
        sum += val[st - 1] - val[pre];
        if (edd >= st) {
          int l = 31 - __builtin_clz(edd - st + 1);
          mx = max(mx, max(mxx[st][l], mxx[edd - (1 << l) + 1][l]));
        }
        sum += mx;
        pre = edd;
      }
      sum += val[cur] - val[pre];
      printf("%d\n", n - sum);
    }
    if (ok) return 0;
    for (register int j = i; j < ed; j++) {
      int pos = p[j].first, va = p[j].second;
      s[a[pos]].erase(pos);
      cnt[a[pos]]--;
      int pp = fir[a[pos]];
      if (s[a[pos]].empty())
        fir[a[pos]] = last[a[pos]] = 0;
      else
        fir[a[pos]] = *s[a[pos]].begin(), last[a[pos]] = *s[a[pos]].rbegin();
      if (pp != fir[a[pos]]) {
        int k;
        for (k = 0; k < nn; k++)
          if (q[k] == a[pos]) break;
        while (k + 1 < nn && fir[q[k + 1]] < fir[q[k]])
          swap(q[k], q[k + 1]), k++;
        while (k && fir[q[k - 1]] > fir[q[k]]) swap(q[k], q[k - 1]), k--;
      }
      a[pos] = va;
      s[va].insert(pos);
      cnt[va]++;
      pp = fir[va];
      fir[va] = *s[va].begin(), last[va] = *s[va].rbegin();
      if (pp != fir[va]) {
        int k;
        for (k = 0; k < nn; k++)
          if (q[k] == va) break;
        while (k + 1 < nn && fir[q[k + 1]] < fir[q[k]])
          swap(q[k], q[k + 1]), k++;
        while (k && fir[q[k - 1]] > fir[q[k]]) swap(q[k], q[k - 1]), k--;
      }
      int sum = 0;
      int pre = 0;
      for (register int i = 0, j = 0; i < nn; i = j) {
        if (fir[q[i]] == 0) {
          j++;
          continue;
        }
        int now = last[q[i]], mx = 0;
        while (1) {
          while (j < nn && now >= fir[q[j]])
            now = max(now, last[q[j]]), mx = max(mx, cnt[q[j]]), j++;
          if (id[now] < 0 || now == R[id[now]]) break;
          now = R[id[now]];
        }
        int st = id[fir[q[i]]] < 0 ? -id[fir[q[i]]] : id[fir[q[i]]];
        int edd = id[now] < 0 ? -id[now] - 1 : id[now];
        sum += val[st - 1] - val[pre];
        if (edd >= st) {
          int l = 31 - __builtin_clz(edd - st + 1);
          mx = max(mx, max(mxx[st][l], mxx[edd - (1 << l) + 1][l]));
        }
        sum += mx;
        pre = edd;
      }
      sum += val[cur] - val[pre];
      printf("%d\n", n - sum);
    }
  }
  return 0;
}
