#include <iostream>

using namespace std;

const int MAX_N = 4e5 + 10;
const int ZERO = 2e5 + 5;

int _cover [MAX_N];
int& cover (int x) {
  return _cover[ZERO + x];
}

int ans = 0;
int cnt [MAX_N];

void add (int x) {
  cnt[x]++;
  int pos = x - cnt[x] + 1;

  cover(pos)++;
  if (pos > 0 && cover(pos) == 1) ans++;
}

void del (int x) {
  int pos = x - cnt[x] + 1;
  cnt[x]--;

  cover(pos)--;
  if (pos > 0 && cover(pos) == 0) ans--;
}

int arr [MAX_N];

int main () {
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
    add(arr[i]);
  }

  for (int i = 0; i < m; i++) {
    int idx, val;
    cin >> idx >> val;

    del(arr[idx]);
    arr[idx] = val;
    add(arr[idx]);
    cout << n - ans << '\n';
  }
}
