#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n,m;
int a[200010];
int cnt[200010];
int sum[200010];
int ans;
void upd(int x,int v)
{
	if(x>cnt[x])
	{
		sum[x-cnt[x]]+=v;
		if(v==1 && sum[x-cnt[x]]==1)ans--;
		if(v==-1 && sum[x-cnt[x]]==0)ans++;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	ans=n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		upd(a[i],1);
		cnt[a[i]]++;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		cnt[a[x]]--;
		upd(a[x],-1);
		upd(y,1);
		cnt[y]++;
		a[x]=y;
		printf("%d\n",ans);
	}
	return 0;
} 