#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,m,ans,a[maxn],cnt[maxn],sum[maxn];
void judge(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()
{
	cin>>n>>m;
	ans=n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		judge(a[i],1);
		cnt[a[i]]++;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		cnt[a[x]]--;
		judge(a[x],-1);
		judge(y,1);
		cnt[y]++;
		a[x]=y;
		cout<<ans<<endl;
	}
	return 0;
}