#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;

const int N=200005;

int n,T,ans,x,w,y;
int cnt[N],a[N],b[N];

int main(){
	int i,j;
	scanf("%d%d",&n,&T);
	for (i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++;
	for (i=1;i<=n;i++){
		for (j=max(0,i-cnt[i]);j<i;j++) b[j]++;
	}
	for (i=0;i<n;i++)
		if (!b[i]) ans++;
	while (T--){
		scanf("%d%d",&x,&w);
		y=a[x]-cnt[a[x]];
		if (y>=0){
			b[y]--;
			if (!b[y]) ans++;
		}
		cnt[a[x]]--;
		a[x]=w; cnt[a[x]]++;
		y=a[x]-cnt[a[x]];
		if (y>=0){
			if (!b[y]) ans--;
			b[y]++;
		}
		printf("%d\n",ans);
	}
	return 0;
}