#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,t1,ans,a[500010],b[500010],cnt[500010];
void ins(int x){
	if(x<1)return;
	if(!cnt[x])ans++;
	cnt[x]++;
}
void dec(int x){
	if(x<1)return;
	if(cnt[x]==1)ans--;
	cnt[x]--;
}
int main(){
	int i,x,y;
	scanf("%d%d",&n,&t1);
	for(i=1;i<=n;i++){
		scanf("%d",&x);a[x]++;
		ins(x-a[x]+1);
		b[i]=x;
	}
	while(t1--){
		scanf("%d%d",&x,&y);
		dec(b[x]-a[b[x]]+1);a[b[x]]--;
		b[x]=y;a[y]++;
		ins(y-a[y]+1);
		printf("%d\n",n-ans);
	}
}