#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
string direc = "URDL";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
int a[200135], Q;
set<int> pos[200135];
const int MN = (1 << 20) + 5;
struct mb {
  int M, T[MN];
  void init(int sz) {
    for (M = 1; sz + 2 > M; M <<= 1)
      ;
  }
  void init(int sz, int val) {
    for (M = 1; sz + 2 > M; M <<= 1)
      ;
    for (int(i) = 0; (i) < (int)(MN); (i)++) T[i] = val;
  }
  void clear() { memset(T, 0, sizeof T); }
  void upt(int l, int val) {
    l += M;
    T[l] = val;
    while (l > 1) {
      T[l >> 1] = max(T[l], T[l ^ 1]);
      l >>= 1;
    }
  }
  int qyRangeMax(int l, int r) {
    if (r < l) return 0;
    int ans = 0;
    for (l = l + M - 1, r = r + M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) ans = max(ans, T[l ^ 1]);
      if (r & 1) ans = max(ans, T[r ^ 1]);
    }
    return ans;
  }
} T1;
struct nd {
  int lp, rp, mi, sum;
  nd() { lp = rp = mi = sum = 0; }
  friend nd operator+(const nd &x, const nd &y) {
    nd res = nd();
    if (x.mi < y.mi)
      res = x;
    else if (y.mi < x.mi)
      res = y;
    else {
      res.mi = x.mi;
      res.lp = x.lp;
      res.rp = y.rp;
      res.sum = x.sum + y.sum + T1.qyRangeMax(x.rp, y.lp - 1);
    }
    return res;
  }
  void addlz(int val) { mi += val; }
} T[200135 * 4];
int lz[200135 * 4];
void Up(int rt, int l, int r) { T[rt] = T[(rt << 1)] + T[(rt << 1 | 1)]; }
void Down(int rt, int l, int r) {
  if (lz[rt] != 0) {
    T[(rt << 1)].addlz(lz[rt]);
    lz[(rt << 1)] += lz[rt];
    T[(rt << 1 | 1)].addlz(lz[rt]);
    lz[(rt << 1 | 1)] += lz[rt];
    lz[rt] = 0;
  }
}
void build(int rt, int l, int r) {
  if (l == r) {
    T[rt].lp = r;
    T[rt].rp = r;
    return;
  }
  int mid = (l + r) / 2;
  build((rt << 1), l, mid);
  build((rt << 1 | 1), mid + 1, r);
  Up(rt, l, r);
}
void upt(int rt, int l, int r, int L, int R, int val) {
  if (R < L) return;
  if (R < l || r < L) return;
  if (L <= l && r <= R) {
    T[rt].addlz(val);
    lz[rt] += val;
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  upt((rt << 1), l, mid, L, R, val);
  upt((rt << 1 | 1), mid + 1, r, L, R, val);
  Up(rt, l, r);
}
void upt1(int rt, int l, int r, int L, int val) {
  if (l == r) {
    T1.upt(L, val);
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  if (L <= mid)
    upt1((rt << 1), l, mid, L, val);
  else
    upt1((rt << 1 | 1), mid + 1, r, L, val);
  Up(rt, l, r);
}
void modify(int x, int sig) {
  if (pos[x].empty()) return;
  upt1(1, 1, n + 1, *pos[x].begin(), sig * pos[x].size());
  upt(1, 1, n + 1, *pos[x].begin() + 1, *pos[x].rbegin(), sig);
}
void fmain(int tid) {
  scanf("%d%d", &n, &Q);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%d", a + i);
    pos[a[i]].insert(i);
  }
  T1.init(n);
  for (int(i) = 1; (i) <= (int)(200135 - 5); (i)++)
    if (!pos[i].empty()) {
      T1.upt(*pos[i].begin(), (int)pos[i].size());
    }
  build(1, 1, n + 1);
  for (int(i) = 1; (i) <= (int)(200135 - 5); (i)++)
    if (!pos[i].empty()) {
      upt(1, 1, n + 1, *pos[i].begin() + 1, *pos[i].rbegin(), 1);
    }
  printf("%d\n", n - T[1].sum);
  for (int(i) = 1; (i) <= (int)(Q); (i)++) {
    int j, x;
    scanf("%d%d", &j, &x);
    int val = a[j];
    a[j] = x;
    modify(val, -1);
    pos[val].erase(j);
    modify(val, 1);
    modify(x, -1);
    pos[x].insert(j);
    modify(x, 1);
    printf("%d\n", n - T[1].sum);
  }
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
