# include <bits/stdc++.h>
using namespace std;

int ball[200005], cnt[200005];
int cover[200005];
int main(){

  ios_base :: sync_with_stdio(false);

  int n, q;
  cin >> n >> q;
  for(int i=1; i<=n; i++){
    cin >> ball[i];
    cnt[ball[i]]++;
  }

  for(int i=1; i<=n; i++){
    for(int j=max(0, i-cnt[i]+1); j<=i; j++){
      cover[j]++;
    }
  }

  int ans = 0;
  for(int i=1; i<=n; i++){
    ans += (cover[i] == 0);
  }

  while(q--){
    int idx, num;
    cin >> idx >> num;

    int b = ball[idx];
    
    int left = b - cnt[b] + 1;
    if(left > 0){
      cover[left]--;
      if(cover[left] == 0) ans++;
    }
    cnt[b]--;

    left = num - cnt[num];
    if(left > 0){
      cover[left]++;
      if(cover[left] == 1) ans--;
    }

    ball[idx] = num;
    cnt[num]++;
    cout << ans << endl;
  }


  return 0;
}