#include <bits/stdc++.h>
using std::cerr;
using std::endl;
inline int rd() {
  int b = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return b;
}
const int N = 2e5 + 233;
int n, q, A[N];
std::set<int> set[N];
struct SegTree {
  int min_val, max_cnt;
  int lcnt, rcnt;
  int ans;
  int tag;
} seg[N * 4];
inline void pushup(int p) {
  seg[p].min_val = std::min(seg[(p << 1)].min_val, seg[((p << 1) | 1)].min_val);
  seg[p].max_cnt = std::max(seg[(p << 1)].max_cnt, seg[((p << 1) | 1)].max_cnt);
  if (seg[(p << 1)].min_val == seg[((p << 1) | 1)].min_val) {
    seg[p].ans = seg[(p << 1)].ans + seg[((p << 1) | 1)].ans;
    seg[p].ans += std::max(seg[(p << 1)].rcnt, seg[((p << 1) | 1)].lcnt);
    seg[p].lcnt = seg[(p << 1)].lcnt;
    seg[p].rcnt = seg[((p << 1) | 1)].rcnt;
  } else if (seg[(p << 1)].min_val < seg[((p << 1) | 1)].min_val) {
    seg[p].ans = seg[(p << 1)].ans;
    seg[p].lcnt = seg[(p << 1)].lcnt;
    seg[p].rcnt = std::max(seg[(p << 1)].rcnt, seg[((p << 1) | 1)].max_cnt);
  } else {
    seg[p].ans = seg[((p << 1) | 1)].ans;
    seg[p].rcnt = seg[((p << 1) | 1)].rcnt;
    seg[p].lcnt = std::max(seg[((p << 1) | 1)].lcnt, seg[(p << 1)].max_cnt);
  }
}
inline void push(int p, int v) {
  seg[p].min_val += v;
  seg[p].tag += v;
}
inline void pushdown(int p) {
  if (seg[p].tag) {
    push((p << 1), seg[p].tag);
    push(((p << 1) | 1), seg[p].tag);
    seg[p].tag = 0;
  }
}
void modify1(int p, int x, int v, int L, int R) {
  if (L == R) {
    seg[p].max_cnt = seg[p].lcnt = v;
    return;
  }
  pushdown(p);
  if (x <= ((L + R) >> 1))
    modify1((p << 1), x, v, L, ((L + R) >> 1));
  else
    modify1(((p << 1) | 1), x, v, ((L + R) >> 1) + 1, R);
  pushup(p);
}
void modify2(int p, int l, int r, int v, int L, int R) {
  if (l <= L && r >= R) {
    push(p, v);
    return;
  }
  pushdown(p);
  if (l <= ((L + R) >> 1)) modify2((p << 1), l, r, v, L, ((L + R) >> 1));
  if (r > ((L + R) >> 1))
    modify2(((p << 1) | 1), l, r, v, ((L + R) >> 1) + 1, R);
  pushup(p);
}
inline void modify(int x, int o) {
  if (set[x].empty()) return;
  modify1(1, *set[x].begin(), o == 1 ? (int)set[x].size() : 0, 1, n);
  if (set[x].size() > 1)
    modify2(1, *set[x].begin(), *(--set[x].end()) - 1, o, 1, n);
}
inline int query() { return n - (seg[1].ans + seg[1].lcnt + seg[1].rcnt); }
int main() {
  n = rd(), q = rd();
  for (int i = 1; i <= n; ++i) {
    A[i] = rd();
    set[A[i]].insert(i);
  }
  for (int i = 1; i < N; ++i) modify(i, 1);
  printf("%d\n", query());
  while (q--) {
    int x = rd(), v = rd();
    modify(A[x], -1);
    set[A[x]].erase(x);
    modify(A[x], 1);
    modify(v, -1);
    set[v].insert(x);
    A[x] = v;
    modify(v, 1);
    printf("%d\n", query());
  }
  return 0;
}
