#include<cstdio>
#include<queue>
#include<set>
using namespace std;
const int maxn=200005;
int sz[maxn];
int a[maxn];
int cvr[maxn],cntcvr=0;
int main(){
  int n,m;scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i)scanf("%d",a+i);
  for(int i=1;i<=n;++i){
    if(1<=a[i]-sz[a[i]]&&a[i]-sz[a[i]]<=n){
      cvr[a[i]-sz[a[i]]]++;
      if(cvr[a[i]-sz[a[i]]]==1)cntcvr++;
    }
    sz[a[i]]++;
  }
  int x,y;
  while(m--){
    scanf("%d%d",&x,&y);
    sz[a[x]]--;
    if(1<=a[x]-sz[a[x]]&&a[x]-sz[a[x]]<=n){
      cvr[a[x]-sz[a[x]]]--;
      if(cvr[a[x]-sz[a[x]]]==0)cntcvr--;
    }
    a[x]=y;
    if(1<=a[x]-sz[a[x]]&&a[x]-sz[a[x]]<=n){
      cvr[a[x]-sz[a[x]]]++;
      if(cvr[a[x]-sz[a[x]]]==1)cntcvr++;
    }
    sz[a[x]]++;
    printf("%d\n",n-cntcvr);
  }
  return 0;
}
