#include <cstdio>
#include <algorithm>
#include <cstring>
#define MN 200005
using namespace std;
int mp[MN],a[MN],sm[MN];
int tot,n,m;

inline int read()
{
	int n=0,f=1; char c=getchar();
	while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
	while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
	return n*f;
}

int main()
{
	register int i,j,x,y;
	n=read(); m=read();
	for (i=1;i<=n;++i) ++mp[a[i]=read()];
	for (i=1;i<=n;++i)
		for (j=0;j<i&&j<mp[i];++j)
			if (sm[i-j]++==0) ++tot;
	while (m--)
	{
		x=read(); y=read();
		--mp[a[x]];
		if (mp[a[x]]<a[x])
			if (--sm[a[x]-mp[a[x]]]==0) --tot;
		if (mp[y]<y)
			if (sm[y-mp[y]]++==0) ++tot;
		++mp[y]; a[x]=y;
		printf("%d\n",n-tot);
	}
}