#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=200005;
int read(){
	int x=0,f=1; char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int f[N],a[N],cnt[N];
int main(){
	int n=read(),m=read();
	for (int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++;
	for (int i=1;i<=n;i++){
		if (cnt[i]){
			for (int j=max(0,i-cnt[i]);j<i;j++) f[j]++;
		}
	}
	int ans=0;
	for (int i=0;i<n;i++){
	if (!f[i]) ans++;  }
	for (int i=1;i<=m;i++){
		int u=read(),y=read();
		int x=a[u];
		a[u]=y;
		if (x-cnt[x]>=0){
			f[x-cnt[x]]--;
			if (f[x-cnt[x]]==0) ans++;
		}
		cnt[x]--;
		if (y-cnt[y]-1>=0){
			f[y-cnt[y]-1]++;
			if (f[y-cnt[y]-1]==1) ans--;
		}
		cnt[y]++;
		printf("%d\n",ans);
	}
	return 0;
}