#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int x[N], cnt[N], cov[N];

int main()
{
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x[i]);
    ++cnt[x[i]];
  }
  int ans = n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= cnt[i]; ++j) {
      if (i - j < 0)
        continue;
      if (cov[i - j] == 0)
        --ans;
      ++cov[i - j];
    }
  }
  while (m--) {
    int u, v;
    scanf("%d %d", &u, &v);
    int change = x[u] - cnt[x[u]];
    if (change >= 0) {
      if (cov[change] == 1)
        ++ans;
      --cov[change];
    }
    --cnt[x[u]];
    x[u] = v;
    ++cnt[x[u]];
    change = x[u] - cnt[x[u]];
    if (change >= 0) {
      if (cov[change] == 0)
        --ans;
      ++cov[change];
    }
    printf("%d\n", ans);
  }
  return 0;
}