#include <bits/stdc++.h>

using namespace std;


#define MAXN 200001
int n, m, a[MAXN], h[MAXN], r[MAXN], ans;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    h[a[i]]++;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = max(i-h[i]+1, 1); j <= i; ++j) {
      if (!r[j]) ans++;
      r[j]++;
    }
  }
  for (int i = 0; i < m; ++i) {
    int ii, v;
    cin >> ii >> v;
    int ri = a[ii]-h[a[ii]]+1;
    if (ri>0) {
      r[ri]--;
      if (!r[ri]) ans--;
    }
    h[a[ii]]--;

    a[ii] = v;

    h[a[ii]]++;
    ri = a[ii]-h[a[ii]]+1;
    if (ri>0) {
      if (!r[ri]) ans++;
      r[ri]++;
    }
    cout << n-ans << endl;
  }
  return 0;
}
