#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
const int MX = 1 << 18;
struct NOD {
  int mn, lazy, lmx, rmx, tmx, mxsum;
} seg[2 * MX];
int N;
int A[MAXN];
int cnt[MAXN], cvr[MAXN];
set<int> s[MAXN];
NOD mergenod(NOD &n1, NOD &n2, int l) {
  NOD r;
  r.mn = min(n1.mn, n2.mn) + l;
  r.lazy = l;
  r.lmx = n1.mn <= n2.mn ? n1.lmx : max(n1.tmx, n2.lmx);
  r.rmx = n2.mn <= n1.mn ? n2.rmx : max(n1.rmx, n2.tmx);
  r.tmx = max(n1.tmx, n2.tmx);
  if (n1.mn < n2.mn)
    r.mxsum = n1.mxsum - n1.rmx + r.rmx;
  else if (n1.mn > n2.mn)
    r.mxsum = r.lmx + n2.mxsum - n2.lmx;
  else
    r.mxsum = n1.mxsum - n1.rmx + n2.mxsum - n2.lmx + max(n1.rmx, n2.lmx);
  return r;
}
void updnod(int idx, int l) {
  seg[idx].lmx = seg[idx].tmx = seg[idx].mxsum = cnt[l];
}
void mkseg(int idx, int l, int r) {
  if (l == r) {
    seg[idx].mn = cvr[l];
    updnod(idx, l);
  } else {
    int m = (l + r) / 2;
    mkseg(idx * 2, l, m);
    mkseg(idx * 2 + 1, m + 1, r);
    seg[idx] = mergenod(seg[idx * 2], seg[idx * 2 + 1], 0);
  }
}
void updseg(int idx, int l, int r, int x, int y, int z) {
  if (l == r) updnod(idx, l);
  if (x <= l && r <= y) {
    seg[idx].mn += z;
    seg[idx].lazy += z;
  } else if (l <= y && x <= r) {
    int m = (l + r) / 2;
    updseg(idx * 2, l, m, x, y, z);
    updseg(idx * 2 + 1, m + 1, r, x, y, z);
    seg[idx] = mergenod(seg[idx * 2], seg[idx * 2 + 1], seg[idx].lazy);
  }
}
void updseg(int x, int y, int z) { updseg(1, 0, N - 1, x, y, z); }
void updcnt(int x) { updseg(1, 0, N - 1, x, x, 0); }
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int Q;
  cin >> N >> Q;
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++) {
    if (!s[A[i]].empty()) {
      cvr[*prev(s[A[i]].end())]++;
      cvr[i]--;
    }
    s[A[i]].insert(i);
    cnt[*s[A[i]].begin()]++;
  }
  for (int i = 1; i < N; i++) cvr[i] += cvr[i - 1];
  mkseg(1, 0, N - 1);
  cout << N - seg[1].mxsum << "\n";
  while (Q--) {
    int x, y;
    cin >> x >> y;
    x--;
    s[A[x]].erase(x);
    if (!s[A[x]].empty()) {
      if (x < *s[A[x]].begin()) {
        cnt[*s[A[x]].begin()] = cnt[x] - 1;
        updseg(x, *s[A[x]].begin() - 1, -1);
      } else
        cnt[*s[A[x]].begin()]--;
      updcnt(*s[A[x]].begin());
      if (x > *prev(s[A[x]].end())) updseg(*prev(s[A[x]].end()), x - 1, -1);
    }
    A[x] = y;
    if (!s[y].empty()) {
      if (x < *s[y].begin()) {
        cnt[x] = cnt[*s[y].begin()] + 1;
        cnt[*s[y].begin()] = 0;
        updseg(x, *s[y].begin() - 1, 1);
      } else {
        cnt[x] = 0;
        cnt[*s[y].begin()]++;
      }
      updcnt(*s[y].begin());
      if (x > *prev(s[y].end())) updseg(*prev(s[y].end()), x - 1, 1);
    } else
      cnt[x] = 1;
    updcnt(x);
    s[y].insert(x);
    cout << N - seg[1].mxsum << "\n";
  }
  return 0;
}
