#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
int a[N], w[N], b[N], n, q, p, x;
bool vis[N];
set<int> st[N];
struct node {
  int tag, mn, mx, l, r, all, cnt;
} tr[1 << 19];
void pushup(int k, int l, int r) {
  int lk = k * 2 + 1, rk = k * 2 + 2, mid = (l + r) >> 1;
  tr[k].mn = min(tr[lk].mn, tr[rk].mn);
  tr[k].mx = max(tr[lk].mx, tr[rk].mx);
  tr[k].l = (tr[k].mn == tr[lk].mn) ? tr[lk].l : max(tr[lk].mx, tr[rk].l);
  tr[k].r = (tr[k].mn == tr[rk].mn) ? tr[rk].r : max(tr[lk].r, tr[rk].mx);
  if (tr[k].mn != tr[lk].mn) {
    tr[k].cnt = tr[rk].cnt;
    tr[k].all = tr[rk].all + mid - l + 1;
  } else if (tr[k].mn != tr[rk].mn) {
    tr[k].cnt = tr[lk].cnt;
    tr[k].all = tr[lk].all + r - mid;
  } else {
    tr[k].cnt = tr[lk].cnt + tr[rk].cnt;
    tr[k].all = tr[lk].all + tr[rk].all;
    if (tr[lk].r != -1 || tr[rk].l != -1) {
      tr[k].cnt += max(tr[lk].r, tr[rk].l);
      tr[k].all++;
    }
  }
}
void pushdown(int k) {
  if (tr[k].tag) {
    int lk = k * 2 + 1, rk = k * 2 + 2;
    tr[lk].tag += tr[k].tag;
    tr[rk].tag += tr[k].tag;
    tr[lk].mn += tr[k].tag;
    tr[rk].mn += tr[k].tag;
    tr[k].tag = 0;
  }
}
void build(int k, int l, int r) {
  tr[k].tag = 0;
  if (l == r) {
    tr[k].all = tr[k].cnt = 0;
    tr[k].l = tr[k].r = -1;
    tr[k].mn = b[l];
    tr[k].mx = max(w[l], w[l + 1]);
    return;
  }
  int lk = k * 2 + 1, rk = k * 2 + 2, mid = (l + r) >> 1;
  build(lk, l, mid);
  build(rk, mid + 1, r);
  pushup(k, l, r);
}
void update(int p, int k, int l, int r) {
  if (p < l || p > r) return;
  if (l == r) {
    tr[k].mx = max(w[l], w[l + 1]);
    return;
  }
  int lk = k * 2 + 1, rk = k * 2 + 2, mid = (l + r) >> 1;
  pushdown(k);
  update(p, lk, l, mid);
  update(p, rk, mid + 1, r);
  pushup(k, l, r);
}
void modify(int a, int b, int c, int k, int l, int r) {
  if (a > r || b < l) return;
  if (a <= l && r <= b) {
    tr[k].tag += c;
    tr[k].mn += c;
    return;
  }
  int lk = k * 2 + 1, rk = k * 2 + 2, mid = (l + r) >> 1;
  pushdown(k);
  modify(a, b, c, lk, l, mid);
  modify(a, b, c, rk, mid + 1, r);
  pushup(k, l, r);
}
void add(int p, int x) {
  if (!st[x].empty()) {
    int l = *st[x].begin(), r = *st[x].rbegin();
    if (l < r) modify(l, r - 1, -1, 0, 0, n);
    w[l] = 0;
    update(l - 1, 0, 0, n);
    update(l, 0, 0, n);
  }
  st[x].insert(p);
  int l = *st[x].begin(), r = *st[x].rbegin();
  if (l < r) modify(l, r - 1, 1, 0, 0, n);
  w[l] = st[x].size();
  update(l - 1, 0, 0, n);
  update(l, 0, 0, n);
}
void del(int p, int x) {
  int l = *st[x].begin(), r = *st[x].rbegin();
  if (l < r) modify(l, r - 1, -1, 0, 0, n);
  w[l] = 0;
  update(l - 1, 0, 0, n);
  update(l, 0, 0, n);
  st[x].erase(p);
  if (!st[x].empty()) {
    int l = *st[x].begin(), r = *st[x].rbegin();
    if (l < r) modify(l, r - 1, 1, 0, 0, n);
    w[l] = st[x].size();
    update(l - 1, 0, 0, n);
    update(l, 0, 0, n);
  }
}
void debug(int k, int l, int r) {
  if (l != r) {
    int lk = k * 2 + 1, rk = k * 2 + 2, mid = (l + r) >> 1;
    pushdown(k);
    debug(lk, l, mid);
    debug(rk, mid + 1, r);
    pushup(k, l, r);
  }
  printf("%d %d %d %d %d %d\n", l, r, tr[k].l, tr[k].r, tr[k].cnt, tr[k].all);
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    st[a[i]].insert(i);
    vis[a[i]] = false;
  }
  for (int i = 1; i <= n; ++i) {
    if (vis[a[i]]) continue;
    vis[a[i]] = true;
    int l = *st[a[i]].begin(), r = *st[a[i]].rbegin();
    w[l] = st[a[i]].size();
    if (l <= r - 1) b[l]++, b[r]--;
  }
  for (int i = 1; i <= n; ++i) b[i] += b[i - 1];
  build(0, 0, n);
  printf("%d\n", tr[0].all - tr[0].cnt);
  while (q--) {
    scanf("%d %d", &p, &x);
    del(p, a[p]);
    a[p] = x;
    add(p, a[p]);
    printf("%d\n", tr[0].all - tr[0].cnt);
  }
}
