#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, q, ans, A[N], ar[N], cnt[N];

void add(int x) {
	int l = max(0, x - cnt[x]);
	cnt[x]++;
	ar[l]++;
	if (ar[l] == 1)
		ans--;
}

void del(int x) {
	cnt[x]--;
	int l = max(0, x - cnt[x]);
	ar[l]--;
	if (!ar[l])
		ans++;
}

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q;
	ans = n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		x--;
		add(x);
		A[i] = x;
	}
	
	while (q--) {
		int indx, x;
		cin >> indx >> x;
		x--; indx--;
		del(A[indx]);
		A[indx] = x;
		add(x);
		
		cout << ans << '\n';
	}
}