#include<bits/stdc++.h>
using namespace std;
int n,m,cnt[200005],a[200005],cover[200005],ans;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read(),cnt[a[i]]++,cover[a[i]-cnt[a[i]]+1]++;
	for(int i=1;i<=n;++i) if(cover[i]==0) ans++;
	for(int i=1;i<=m;++i){
		int x,y;
		x=read(),y=read();
		cnt[a[x]]--; if(a[x]-cnt[a[x]]>0){cover[a[x]-cnt[a[x]]]--; if(cover[a[x]-cnt[a[x]]]==0) ans++;}
		cnt[y]++; if(y-cnt[y]+1>0){cover[y-cnt[y]+1]++; if(cover[y-cnt[y]+1]==1) ans--;}
		a[x]=y;
		printf("%d\n",ans);
	}
}