#include <bits/stdc++.h>
using namespace std;
const int inf = 2147483647;
const int N = 2e5 + 1;
int _max(int x, int y) { return x > y ? x : y; }
int _min(int x, int y) { return x < y ? x : y; }
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * f;
}
void put(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) put(x / 10);
  putchar(x % 10 + '0');
}
int gg[N];
struct tnode {
  int mx[N << 2], mn[N << 2], ans[N << 2], cnt[N << 2], lmx[N << 2],
      rmx[N << 2], lzy[N << 2];
  void pushup(int u, int l, int r) {
    int mid = l + r >> 1;
    mx[u] = _max(mx[u << 1], mx[u << 1 | 1]);
    mn[u] = _min(mn[u << 1], mn[u << 1 | 1]);
    if (mn[u] == mn[u << 1])
      lmx[u] = lmx[u << 1];
    else
      lmx[u] = _max(lmx[u << 1 | 1], mx[u << 1]);
    if (mn[u] == mn[u << 1 | 1])
      rmx[u] = rmx[u << 1 | 1];
    else
      rmx[u] = _max(rmx[u << 1], mx[u << 1 | 1]);
    if (mn[u] != mn[u << 1])
      ans[u] = ans[u << 1 | 1], cnt[u] = cnt[u << 1 | 1] + mid - l + 1;
    else if (mn[u] != mn[u << 1 | 1])
      ans[u] = ans[u << 1], cnt[u] = cnt[u << 1] + r - mid;
    else {
      ans[u] = ans[u << 1] + ans[u << 1 | 1],
      cnt[u] = cnt[u << 1] + cnt[u << 1 | 1];
      if (rmx[u << 1] != -1 || lmx[u << 1 | 1] != -1)
        ans[u] += _max(rmx[u << 1], lmx[u << 1 | 1]), cnt[u]++;
    }
  }
  void pushdown(int u) {
    if (!lzy[u]) return;
    mn[u << 1] += lzy[u], lzy[u << 1] += lzy[u];
    mn[u << 1 | 1] += lzy[u], lzy[u << 1 | 1] += lzy[u];
    lzy[u] = 0;
  }
  void update(int u, int l, int r, int p) {
    if (l == r) {
      mx[u] = _max(gg[l + 1], gg[l]);
      return;
    }
    int mid = l + r >> 1;
    pushdown(u);
    if (p <= mid)
      update(u << 1, l, mid, p);
    else
      update(u << 1 | 1, mid + 1, r, p);
    pushup(u, l, r);
  }
  void change(int u, int l, int r, int ll, int rr, int c) {
    if (ll > rr) return;
    if (l == ll && r == rr) {
      mn[u] += c, lzy[u] += c;
      return;
    }
    pushdown(u);
    int mid = l + r >> 1;
    if (rr <= mid)
      change(u << 1, l, mid, ll, rr, c);
    else if (ll > mid)
      change(u << 1 | 1, mid + 1, r, ll, rr, c);
    else
      change(u << 1, l, mid, ll, mid, c),
          change(u << 1 | 1, mid + 1, r, mid + 1, rr, c);
    pushup(u, l, r);
  }
} t;
int n, a[N];
set<int> q[N];
void update(int p) { t.update(1, 0, n, p - 1), t.update(1, 0, n, p); }
void add(int x) {
  int l, r;
  if (!q[a[x]].empty()) {
    l = *q[a[x]].begin(), r = *q[a[x]].rbegin();
    t.change(1, 0, n, l, r - 1, -1), gg[l] = 0, update(l);
  }
  q[a[x]].insert(x);
  l = *q[a[x]].begin(), r = *q[a[x]].rbegin();
  t.change(1, 0, n, l, r - 1, 1), gg[l] = q[a[x]].size(), update(l);
}
void del(int x) {
  int l, r;
  l = *q[a[x]].begin(), r = *q[a[x]].rbegin();
  t.change(1, 0, n, l, r - 1, -1), gg[l] = 0, update(l);
  q[a[x]].erase(x);
  if (!q[a[x]].empty()) {
    l = *q[a[x]].begin(), r = *q[a[x]].rbegin();
    t.change(1, 0, n, l, r - 1, 1), gg[l] = q[a[x]].size(), update(l);
  }
}
int main() {
  n = read();
  int q = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  memset(t.lmx, -1, sizeof(t.lmx)), memset(t.rmx, -1, sizeof(t.rmx));
  for (int i = 1; i <= n; i++) add(i);
  put(t.cnt[1] - t.ans[1]), puts("");
  while (q--) {
    int x = read(), c = read();
    del(x), a[x] = c, add(x);
    put(t.cnt[1] - t.ans[1]), puts("");
  }
  return 0;
}
