#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
long long n, Q;
long long val[200005 << 2], tag[200005 << 2], cnt[200005 << 2];
long long lmx[200005 << 2], rmx[200005 << 2], sum[200005 << 2];
inline void pushup(long long rt) {
  long long ls = rt << 1;
  long long rs = rt << 1 | 1;
  cnt[rt] = max(cnt[ls], cnt[rs]);
  val[rt] = min(val[ls], val[rs]);
  if (val[ls] < val[rs]) {
    sum[rt] = sum[ls];
    lmx[rt] = lmx[ls];
    rmx[rt] = max(cnt[rs], rmx[ls]);
  } else if (val[ls] > val[rs]) {
    sum[rt] = sum[rs];
    rmx[rt] = rmx[rs];
    lmx[rt] = max(cnt[ls], lmx[rs]);
  } else {
    lmx[rt] = lmx[ls];
    rmx[rt] = rmx[rs];
    sum[rt] = sum[ls] + sum[rs] + max(lmx[rs], rmx[ls]);
  }
}
inline void pusht(long long p, long long v) { val[p] += v, tag[p] += v; }
inline void pushdown(long long p) {
  if (tag[p]) pusht(p << 1, tag[p]), pusht(p << 1 | 1, tag[p]), tag[p] = 0;
}
void mdf_val(long long p, long long l, long long r, long long nl, long long nr,
             long long v) {
  if (nl > nr) return;
  if (l >= nl && r <= nr) return pusht(p, v);
  long long mid = l + r >> 1;
  pushdown(p);
  if (nl <= mid) mdf_val(p << 1, l, mid, nl, nr, v);
  if (nr > mid) mdf_val(p << 1 | 1, mid + 1, r, nl, nr, v);
  pushup(p);
}
void mdf_cnt(long long p, long long l, long long r, long long x, long long v) {
  if (l == r) return cnt[p] = lmx[p] = v, void();
  long long mid = l + r >> 1;
  pushdown(p);
  x <= mid ? mdf_cnt(p << 1, l, mid, x, v)
           : mdf_cnt(p << 1 | 1, mid + 1, r, x, v);
  pushup(p);
}
long long a[200005];
set<long long> s[200005];
inline void mdf(long long c, long long o) {
  if (!s[c].size()) return;
  long long l = *s[c].begin(), r = *(--s[c].end());
  mdf_cnt(1, 1, n, l, (o > 0) * (s[c].size()));
  mdf_val(1, 1, n, l, r - 1, o);
}
inline long long orz() { return n - sum[1] - lmx[1] - rmx[1]; }
signed main() {
  n = read(), Q = read();
  for (register long long i = (1); i <= (n); ++i)
    a[i] = read(), s[a[i]].insert(i);
  for (register long long i = (1); i <= (200000); ++i) mdf(i, 1);
  printf("%d\n", orz());
  for (register long long _ = (1); _ <= (Q); ++_) {
    long long x = read(), y = read(), z = a[x];
    mdf(z, -1), s[z].erase(x), mdf(z, 1);
    mdf(y, -1), s[y].insert(x), mdf(y, 1);
    a[x] = y;
    printf("%d\n", orz());
  }
  return 0;
}
