#include <bits/stdc++.h>
using namespace std;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
struct TRes {
  int mina;
  int gmx, lmx, rmx, smx;
  TRes operator+(TRes r) const {
    if (mina < r.mina)
      return {mina, max(gmx, r.gmx), lmx, max(rmx, r.gmx), smx};
    else if (mina > r.mina)
      return {r.mina, max(gmx, r.gmx), max(gmx, r.lmx), r.rmx, r.smx};
    else
      return {mina, max(gmx, r.gmx), lmx, r.rmx, smx + max(rmx, r.lmx) + r.smx};
  }
};
struct TNode {
  int L, R;
  int l, r;
  int val;
  TRes res;
};
const int maxn = 410000;
int tc = 0;
TNode t[maxn];
int n, q;
int buildTree(int L, int R) {
  int node = tc++;
  TNode &n = t[node];
  n = {L, R, -1, -1, 0, {0, 0, 0, 0, 0}};
  if (R - L > 1) {
    int M = (L + R) / 2;
    n.l = buildTree(L, M);
    n.r = buildTree(M, R);
  }
  return node;
}
void addval(int node, int val) {
  TNode &n = t[node];
  n.val += val;
  n.res.mina += val;
}
void push(int node) {
  TNode &n = t[node];
  addval(n.l, n.val);
  addval(n.r, n.val);
  n.val = 0;
}
void addseg(int node, int L, int R, int delta) {
  TNode &n = t[node];
  if (max(L, n.L) >= min(R, n.R)) return;
  if (L <= n.L && n.R <= R) {
    addval(node, delta);
    return;
  }
  push(node);
  addseg(n.l, L, R, delta);
  addseg(n.r, L, R, delta);
  n.res = t[n.l].res + t[n.r].res;
}
void changenum(int node, int i, int x) {
  TNode &n = t[node];
  if (i < n.L || i >= n.R) return;
  if (n.R - n.L == 1) {
    n.res.lmx = n.res.gmx = x;
    return;
  }
  push(node);
  changenum(n.l, i, x);
  changenum(n.r, i, x);
  n.res = t[n.l].res + t[n.r].res;
}
int a[maxn];
set<int> occs[maxn];
int root;
void update_num(int x, bool undo) {
  if (occs[x].empty()) return;
  addseg(root, *occs[x].begin(), *occs[x].rbegin(), undo ? -1 : 1);
  changenum(root, *occs[x].begin(), undo ? 0 : occs[x].size());
}
void print(int node) {
  if (node == -1) return;
  TNode &n = t[node];
  cerr << n.L << ' ' << n.R << ' ' << n.res.mina << ' ' << n.res.gmx << ' '
       << n.res.lmx << ' ' << n.res.rmx << ' ' << n.res.smx << '\n';
  print(n.l);
  print(n.r);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  cin >> n >> q;
  for (int i = 1; i <= (int)(n); ++i) {
    cin >> a[i];
    occs[a[i]].insert(i);
  }
  root = buildTree(0, n + 2);
  for (int i = 0; i < (int)(maxn); ++i) update_num(i, false);
  cout << n - t[root].res.smx << '\n';
  for (int i = 0; i < (int)(q); ++i) {
    int p, x;
    cin >> p >> x;
    if (x != a[p]) {
      update_num(x, true);
      update_num(a[p], true);
      occs[a[p]].erase(p);
      occs[x].insert(p);
      update_num(x, false);
      update_num(a[p], false);
      a[p] = x;
    }
    auto r = t[root].res;
    assert(r.mina == 0 && r.lmx == 0 && r.rmx == 0);
    cout << n - t[root].res.smx << '\n';
  }
  return 0;
}
