#include <cstdio>
#define N 200005
int n, m, x, y, s, a[N], c[N], v[N];

void f(int p) {
	int t = p - c[p];
	if(t>0) {
		if(v[t]==0) s++;
		v[t]++;
	}
	c[p]++;
}

void g(int p) {
	int t = p - c[p] + 1;
	if(t>0) {
		if(v[t]==1) s--;
		v[t]--;
	}
	c[p]--;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) {
		scanf("%d", a+i);
		f(a[i]);
	}
	while(m--) {
		scanf("%d%d", &x, &y);
		g(a[x]);
		f(y);
		a[x] = y;
		printf("%d\n", n-s);
	}
	return 0;
}