#pragma comment(linker, "/STACK:64000000")
#include <algorithm>
#include <memory.h>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <queue>

using namespace std;
#define prev privet1
#define next privet2
#define y1 privet3
#define rank privet4
#define left privet5
#define right privet6
#define y0 privet7

const double pi = 3.141592653589793238;

struct tt
{
	int pref, suf, ans, len;
	tt(int pref, int suf, int ans, int len) : pref(pref), suf(suf), ans(ans), len(len) { }
	tt() {};
};

tt f[400333];
int i, n, sz, a[100333], m, x, y;

tt combine(tt left, tt right)
{
	tt res;
	if (left.pref == left.len) res.pref = left.pref + right.pref;
	else res.pref = left.pref;
	if (right.suf == right.len) res.suf = right.suf + left.suf;
	else res.suf = right.suf;
	res.ans = max(left.suf + right.pref, max(left.ans, right.ans));
	res.len = left.len + right.len;
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sz = 1;
	while (sz < n)
		sz += sz;
	a[n + 1] = -123;
	for (i = 1; i <= n; i++)
	{
		int x = (int)(a[i + 1] - 1 == a[i]);
		f[i + sz - 1] = tt(x, x, x, 1);
	}
	for (i = n + 1; i <= sz; i++)
		f[i + sz - 1] = tt(0, 0, 0, 1);
	for (i = sz - 1; i > 0; i--)
		f[i] = combine(f[i + i], f[i + i + 1]);
	printf("%d\n", f[1].ans + 1);
	for (i = 1; i <= m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x] = y;
		int z = (int) (a[x] == a[x + 1] - 1);
		f[x + sz - 1] = tt(z, z, z, 1);
		z = (int) ((a[x - 1] == a[x] - 1));
		if (x > 1) f[x + sz - 2] = tt(z, z, z, 1);
		int v = x + sz - 1;
		v = v >> 1;
		while (v > 0)
		{
			f[v] = combine(f[v + v], f[v + v + 1]);
			v >>= 1;
		}
		if (x == 1) 
		{ 
			printf("%d\n", f[1].ans + 1);
			continue;
		}
		v = x + sz - 2;
		v = v >> 1;
		while (v > 0)
		{
			f[v] = combine(f[v + v], f[v + v + 1]);
			v >>= 1;
		}
		printf("%d\n", f[1].ans + 1);
	}
}