#include <cstdio>

const int MN = 200005;

int N, Q, A[MN], C[MN], _S[MN * 2], *S = _S + MN, Ans;

int main() {
	scanf("%d%d", &N, &Q);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), ++C[A[i]];
	for (int i = 1; i <= N; ++i) ++S[i], --S[i - C[i]];
	for (int i = N; i >= -N; --i) S[i] += S[i + 1], Ans += i > 0 && !S[i];
	while (Q--) {
		int p, x;
		scanf("%d%d", &p, &x);
		--C[A[p]];
		if (!--S[A[p] - C[A[p]]]) if (A[p] - C[A[p]] > 0) ++Ans;
		if (!S[x - C[x]]++) if (x - C[x] > 0) --Ans;
		++C[x];
		A[p] = x;
		printf("%d\n", Ans);
	}
	return 0;
}