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

#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n,0);
  vector<int> c(n,0),d(n,0);
  int ans=n;
  for(int i=0;i<n;i++){
    cin >> a[i];
    a[i]--;
    if(a[i]-c[a[i]]>=0){
      if(d[a[i]-c[a[i]]]==0) ans--;
      d[a[i]-c[a[i]]]++;
    }
    c[a[i]]++;
  }
  int x,y;
  for(int i=0;i<m;i++){
    cin >> x >> y;
    x--,y--;
    c[a[x]]--;
    if(a[x]-c[a[x]]>=0){
      if(d[a[x]-c[a[x]]]==1) ans++;
      d[a[x]-c[a[x]]]--;
    }
    a[x]=y;
    if(a[x]-c[a[x]]>=0){
      if(d[a[x]-c[a[x]]]==0) ans--;
      d[a[x]-c[a[x]]]++;
    }
    c[a[x]]++;
    cout << ans << endl;
  }
  return 0;
}
