#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int n,m,a[maxn],b[maxn];
int x,y,cnt[maxn],ans;
int main() {
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		b[a[i]]++;
	}
	for (int i=1;i<=n;i++)
		for (int j=max(i-b[i],0);j<i;j++)
			cnt[j]++;
	ans=0;
	for (int i=0;i<n;i++)
		if (cnt[i]==0)
			ans++;
	for (int i=1;i<=m;i++) {
		scanf("%d %d",&x,&y);
		if (a[x]-b[a[x]]>=0) {
			cnt[a[x]-b[a[x]]]--;
			if (cnt[a[x]-b[a[x]]]==0)
				ans++;
		}
		b[a[x]]--;
		b[y]++;
		if (y-b[y]>=0) {
			cnt[y-b[y]]++;
			if (cnt[y-b[y]]==1)
				ans--;
		}
		a[x]=y;
		printf("%d\n",ans);
	}
	return 0;
}