#include<cstdio>
#include<algorithm>
using namespace std;
int C[201000], S[201000], n, m, w[201000], r;
void Add(int a) {
	int t = max(a - C[a], 1);
	r -= abs(S[t] - 1);
	S[t]++;
	r += abs(S[t] - 1);
	C[a]++;
}
void Del(int a) {
	C[a]--;
	int t = max(a - C[a], 1);
	r -= abs(S[t] - 1);
	S[t]--;
	r += abs(S[t] - 1);
}
int main() {
	int i, a, b;
	scanf("%d%d", &n, &m);
	r = n;
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		Add(w[i]);
	}
	for (i = 1; i <= m; i++) {
		scanf("%d%d", &a, &b);
		Del(w[a]);
		w[a] = b;
		Add(w[a]);
		printf("%d\n", r / 2);
	}
}