#include <bits/stdc++.h>
using namespace std;
const int B = 200000;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return x * f;
}
int n, Q, a[200010];
set<int> s[200010];
struct Segment_Tree {
  struct node {
    int lmx, rmx, sum, mnc, mxw, add;
    inline void Cov(int d) { mnc += d, add += d; }
  } tree[200010 << 2];
  inline void update(int i) {
    tree[i].mnc = min(tree[i << 1].mnc, tree[i << 1 | 1].mnc);
    tree[i].mxw = max(tree[i << 1].mxw, tree[i << 1 | 1].mxw);
    if (tree[i << 1].mnc < tree[i << 1 | 1].mnc) {
      tree[i].lmx = tree[i << 1].lmx;
      tree[i].rmx = max(tree[i << 1].rmx, tree[i << 1 | 1].mxw);
      tree[i].sum = tree[i << 1].sum;
    } else if (tree[i << 1 | 1].mnc < tree[i << 1].mnc) {
      tree[i].rmx = tree[i << 1 | 1].rmx;
      tree[i].lmx = max(tree[i << 1 | 1].lmx, tree[i << 1].mxw);
      tree[i].sum = tree[i << 1 | 1].sum;
    } else {
      tree[i].lmx = tree[i << 1].lmx;
      tree[i].rmx = tree[i << 1 | 1].rmx;
      tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum +
                    max(tree[i << 1].rmx, tree[i << 1 | 1].lmx);
    }
  }
  inline void pushdown(int i) {
    if (tree[i].add) {
      tree[i << 1].Cov(tree[i].add);
      tree[i << 1 | 1].Cov(tree[i].add);
      tree[i].add = 0;
    }
  }
  void Change(int i, int L, int R, int p, int x) {
    if (L == R) {
      tree[i].mxw = tree[i].lmx = x;
      return;
    }
    pushdown(i);
    int mid = (L + R) >> 1;
    p <= mid ? Change(i << 1, L, mid, p, x)
             : Change(i << 1 | 1, mid + 1, R, p, x);
    update(i);
  }
  void Cover(int i, int L, int R, int l, int r, int x) {
    if (L >= l && R <= r) {
      tree[i].Cov(x);
      return;
    }
    pushdown(i);
    int mid = (L + R) >> 1;
    if (l <= mid) Cover(i << 1, L, mid, l, r, x);
    if (r > mid) Cover(i << 1 | 1, mid + 1, R, l, r, x);
    update(i);
  }
  inline int get_ans() { return tree[1].sum + tree[1].lmx + tree[1].rmx; }
} T;
void Change(int c, int t) {
  int w = s[c].size();
  if (!w) return;
  T.Change(1, 1, n, *s[c].begin(), t > 0 ? w : 0);
  if (w > 1) T.Cover(1, 1, n, *s[c].begin(), (*s[c].rbegin()) - 1, t);
}
int main() {
  n = read(), Q = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    s[a[i]].insert(i);
  }
  for (int i = 1; i <= B; ++i) {
    Change(i, 1);
  }
  printf("%d\n", n - T.get_ans());
  while (Q--) {
    int x = read();
    Change(a[x], -1);
    s[a[x]].erase(x);
    Change(a[x], 1);
    a[x] = read();
    Change(a[x], -1);
    s[a[x]].insert(x);
    Change(a[x], 1);
    printf("%d\n", n - T.get_ans());
  }
  return 0;
}
