#include<cstdio>
#define max(a,b) (a>b?a:b)
#define MaN 200005
#define lson 
int n,m,a[MaN],l,ans=0;
int ton[MaN],mip[MaN],cnt[MaN];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){scanf("%d",&a[i]);ton[a[i]]++;}
	for(int i=1;i<=n;i++){
		mip[i+1]--;
		if(i+1-ton[i]<1){
			mip[1]+=1+ton[i]-i;
			mip[2]-=ton[i]-i;
			continue;
		}
		mip[i+1-ton[i]]++;
	}
	for(int i=1;i<=n;i++){
		cnt[i]=cnt[i-1]+mip[i];
		if(cnt[i]==0) ans++;
	}
	int x,y,ls;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		if(a[x]==y){
			printf("%d\n",ans);
			continue;
		}
		if(!cnt[max(y-ton[y],1)]) ans--;
		cnt[max(y-ton[y],1)]++;
		cnt[max(a[x]+1-ton[a[x]],1)]--;
		if(!cnt[max(a[x]+1-ton[a[x]],1)]) ans++;
		ton[a[x]]--;ton[y]++;
		a[x]=y;
		printf("%d\n",ans);
	}
	return 0;
}