#include <cstdio>
using namespace std;
const int maxn=200001;

int pos[maxn];
int num[maxn];
int a[maxn];
int n,m,ans,old,new_,p;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		num[a[i]]++;
	}
	
	for(int i=1;i<=n;i++) pos[i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i-num[i]+1;j<=i;j++)
		    pos[j]++;
	}
	
	for(int i=1;i<=n;i++) if (!pos[i]) ans++;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&p,&new_);
		old=a[p];
		a[p]=new_;
		
		if (old-num[old]+1>=1)
		{
			pos[old-num[old]+1]--;
			if (!pos[old-num[old]+1]) ans++;
		}
		num[old]--;
		if (new_-num[new_]>=1)
		{
			pos[new_-num[new_]]++;
			if (pos[new_-num[new_]]==1) ans--;
		}
		num[new_]++;
		
		printf("%d\n",ans);
	}
	return 0;
}