#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int now[202020];
int dat[202020];
int ans[202020];
int num, ret;
void add(int a)
{
	if (a + dat[a] < num)
	{
		if (ans[a + dat[a]] == 0)ret--;
		ans[a + dat[a]]++;
	}
	dat[a]++;
}
void sub(int a)
{
	dat[a]--;
	if (a + dat[a] < num)
	{
		ans[a + dat[a]]--;
		if (ans[a + dat[a]] == 0)ret++;
	}
}
int main()
{
	int query;
	scanf("%d%d", &num, &query);
	ret = num;
	for (int i = 0; i < num; i++)
	{
		scanf("%d", &now[i]);
		add(num - now[i]);
	}
	for (int i = 0; i < query; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--;
		sub(num - now[za]);
		now[za] = zb;
		add(num - now[za]);
		printf("%d\n", ret);
	}
}