#include <cstdio>
int N, Q, a[200001], E[200001], O, C[200001];
inline void inc(int x)
{
	if (1 <= x && x <= N && C[x]++ == 0)
		O--;
}
inline void dec(int x)
{
	if (1 <= x && x <= N && --C[x] == 0)
		O++;
}
inline void add(int x)
{
	inc(E[x]--);
}
inline void del(int x)
{
	dec(++E[x]);
}
int main()
{
	scanf("%d%d", &N, &Q);
	for (int i = 1; i <= N; i++)
		E[i] = i;
	O = N;
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", a + i);
		add(a[i]);
	}
	while (Q--)
	{
		int x, w;
		scanf("%d%d", &x, &w);
		del(a[x]);
		a[x] = w;
		add(a[x]);
		printf("%d\n", O);
	}
	return 0;
}
