// SUBSGM Solution. Written by Sergey Kulik

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define maxn 100000 + 5

struct node { // segment tree node
	int l, r, to_left, cnt_left, to_right, cnt_right, best;	
} tree[(maxn) * 4];

int n, m, i, j, k, a[maxn], x;

void unite (int pos) { // union of two sons of a node
	if (tree[pos + pos].to_left != tree[pos + pos + 1].to_left || tree[pos + pos].cnt_left != tree[pos + pos].r - tree[pos].l + 1) {
		tree[pos].to_left = tree[pos + pos].to_left;
		tree[pos].cnt_left = tree[pos + pos].cnt_left;
	} else {
		tree[pos].to_left = tree[pos + pos].to_left;
		tree[pos].cnt_left = tree[pos + pos].cnt_left + tree[pos + pos + 1].cnt_left;
	}
	if (tree[pos + pos + 1].to_right != tree[pos + pos].to_right || tree[pos + pos + 1].cnt_right != tree[pos].r - tree[pos + pos + 1].l + 1) {
		tree[pos].to_right = tree[pos + pos + 1].to_right;
		tree[pos].cnt_right = tree[pos + pos + 1].cnt_right;
	} else {
		tree[pos].to_right = tree[pos + pos + 1].to_right;
		tree[pos].cnt_right = tree[pos + pos + 1].cnt_right + tree[pos + pos].cnt_right;
	}
	tree[pos].best = max(tree[pos + pos].best, tree[pos + pos + 1].best);
	tree[pos].best = max(tree[pos].best, max(tree[pos].cnt_left, tree[pos].cnt_right));
	if (tree[pos + pos].to_right == tree[pos + pos + 1].to_left) 
		tree[pos].best = max(tree[pos].best, tree[pos + pos].cnt_right + tree[pos + pos + 1].cnt_left);
}

void init (int pos, int l, int r) { // segment tree initialization
	tree[pos].l = l, tree[pos].r = r;
	if (l < r) {
		init(pos + pos, l, (l + r) / 2);
		init(pos + pos + 1, (l + r) / 2 + 1, r);
		unite(pos);
	} else {
		tree[pos].to_left = tree[pos].to_right = a[l];
		tree[pos].cnt_left = tree[pos].cnt_right = tree[pos].best = 1;		
	}
}

void change (int pos, int j, int x) { // modifying in a segment tree
	if (tree[pos].l == tree[pos].r) {
		tree[pos].to_left = x;
		tree[pos].to_right = x;
		tree[pos].best = 1;
		tree[pos].cnt_left = 1;
		tree[pos].cnt_right = 1;
	} else {
		if (j <= tree[pos + pos].r) change(pos + pos, j, x); else change(pos + pos + 1, j, x);
		unite(pos);
	}	
}

int main (int argc, char * const argv[]) {
//	freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);	
	for(i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		a[i] -= i; // quite popular trick. If a_i and a_{i-1} are in the same sequence, then a_i will be equal to a_{i-1}
	}
	init(1, 1, n);
	printf("%d\n", tree[1].best); // output the best subsegment of the segment that corresponds to the root node
	for(i = 1; i <= m; i++) {
		scanf("%d %d", &j, &x);
		change(1, j, x - j); // updating using the same trick
		printf("%d\n", tree[1].best); // output the best subsegment of the segment that corresponds to the root node
	}
    return 0;
}