#include<bits/stdc++.h>
using namespace std;
int n,m,a[210000],l[210000],t[210000],ans,cnt[210000],x,y;
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		cnt[a[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		l[i] = i - cnt[i] + 1;
		int ii = i;
		for (int j = max(1,l[i]); j <= i; j++) {
			t[j]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (t[i] == 0) ans++;
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		if (l[a[x]] > 0) {
	 		t[l[a[x]]]--;
			if (t[l[a[x]]] == 0) ans++;
		}
		l[a[x]]++;
		a[x] = y;
		l[y]--;
		if (l[y] > 0) {
			t[l[y]]++;
			if (t[l[y]] == 1) ans--;
		}
		cout<<ans<<endl;
	}
}