#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000001;
const long double EPS = 1e-9;
const int MOD = 1000000007;
const long long LLINF = 1000000000000000001;
const int maxn = (1 << 18);
struct treeNode {
  long long sum;
  int myChange;
  int minVal;
  int bestAll;
  int bestFirst;
  int bestLast;
  treeNode()
      : sum(0), myChange(0), minVal(0), bestAll(0), bestFirst(0), bestLast(0) {}
  void fromMerge(treeNode a, treeNode b) {
    minVal = min(a.minVal, b.minVal) + myChange;
    bestAll = max(a.bestAll, b.bestAll);
    if (a.minVal == b.minVal) {
      bestFirst = a.bestFirst;
      bestLast = b.bestLast;
      sum = a.sum - a.bestLast + b.sum - b.bestFirst +
            max(a.bestLast, b.bestFirst);
    } else if (a.minVal < b.minVal) {
      bestFirst = a.bestFirst;
      bestLast = max(a.bestLast, b.bestAll);
      sum = a.sum - a.bestLast + bestLast;
    } else {
      bestFirst = max(a.bestAll, b.bestFirst);
      bestLast = b.bestLast;
      sum = b.sum - b.bestFirst + bestFirst;
    }
  }
  void setBest(int a) {
    sum = a;
    bestAll = a;
    bestFirst = a;
  }
};
treeNode tree[2 * maxn];
void setBestAll(int a, int p) {
  p += maxn;
  tree[p].setBest(a);
  while (p > 1) {
    p /= 2;
    tree[p].fromMerge(tree[p * 2], tree[p * 2 + 1]);
  }
}
void addOne(int v, int p) {
  tree[p].myChange += v;
  if (p < maxn)
    tree[p].fromMerge(tree[p * 2], tree[p * 2 + 1]);
  else
    tree[p].minVal += v;
}
void segAdd(int v, int a, int b) {
  a += maxn;
  b += maxn;
  if (b < a) return;
  addOne(v, a);
  if (b != a) addOne(v, b);
  while (a / 2 != b / 2) {
    if (a % 2 == 0) addOne(v, a + 1);
    if (b % 2 == 1) addOne(v, b - 1);
    a /= 2;
    b /= 2;
    tree[a].fromMerge(tree[a * 2], tree[a * 2 + 1]);
    tree[b].fromMerge(tree[b * 2], tree[b * 2 + 1]);
  }
  while (a > 1) {
    a /= 2;
    tree[a].fromMerge(tree[a * 2], tree[a * 2 + 1]);
  }
}
int a[maxn];
set<int> positions[maxn];
void addNum(int v) {
  segAdd(1, *positions[v].begin(), *positions[v].rbegin() - 1);
  setBestAll(((int)(positions[v]).size()), *positions[v].rbegin());
}
void reverseNum(int v) {
  segAdd(-1, *positions[v].begin(), *positions[v].rbegin() - 1);
  setBestAll(0, *positions[v].rbegin());
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    positions[a[i]].insert(i);
  }
  segAdd(INF, 0, 0);
  segAdd(INF, n + 1, maxn - 1);
  for (int i = 1; i <= 200000; i++)
    if (!positions[i].empty()) addNum(i);
  cout << n - tree[1].sum << '\n';
  for (int i = 1; i <= q; i++) {
    int p, x;
    cin >> p >> x;
    reverseNum(a[p]);
    positions[a[p]].erase(p);
    if (!positions[a[p]].empty()) addNum(a[p]);
    if (!positions[x].empty()) reverseNum(x);
    positions[x].insert(p);
    addNum(x);
    a[p] = x;
    cout << n - tree[1].sum << '\n';
  }
}
