#include <iostream>
using namespace std;

const int MAXN = 2e5 + 10;
int n, m, ans, cnt[MAXN], r[MAXN], a[MAXN];

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	for (int i = 0; i <= n; i++)
		for (int j = 1; j <= cnt[i]; j++)
			if (i - j >= 0)
				r[i - j]++;
	for (int i = 0; i < n; i++)
		ans += (r[i] == 0);
	for (int i = 0; i < m; i++) {
		int p, c, t;
		cin >> p >> c;
		p--;
		t = a[p] - cnt[a[p]];
		if (t >= 0) {
			r[t]--;
			ans += r[t] == 0;
		}
		cnt[a[p]]--;
		a[p] = c;
		cnt[a[p]]++;
		t = a[p] - cnt[a[p]];
		if (t >= 0) {
			r[t]++;
			ans -= r[t] == 1;
		}
		cout << ans << '\n';
	}
}