#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[200005],b[200005],cnt[200005],x,y,ans;
inline int read(){
	char c=getchar();
	for(;c>'9'||c<'0';) c=getchar();
	int xx=c-'0';
	c=getchar();
	for(;c>='0'&&c<='9';){
		xx=(xx<<3)+(xx<<1)+c-'0';
		c=getchar();
	}
	return xx;
}
int main(){
	n=read(),m=read(),ans=n;
	for(int i=1;i<=n;i++){
		cnt[a[i]=read()]++;
		if(a[i]-cnt[a[i]]>=0){
			if(!b[a[i]-cnt[a[i]]]) ans--;
			b[a[i]-cnt[a[i]]]++;
		}
	}
	for(int i=1;i<=m;i++){
		x=read(),y=read();
		if(a[x]-cnt[a[x]]>=0){
			b[a[x]-cnt[a[x]]]--;
			if(!b[a[x]-cnt[a[x]]]) ans++;
		}
		cnt[a[x]]--,a[x]=y,cnt[y]++;
		if(a[x]-cnt[a[x]]>=0){
			b[a[x]-cnt[a[x]]]++;
			if(b[a[x]-cnt[a[x]]]==1) ans--;
		}
		printf("%d\n",ans);
	}
	return 0;
}