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

struct vert {
	int lewy, pref, sr, suf, prawy;
};

const int N = 500005, z = 8;
vert d[2 * z];
int n, m;

void wstaw(int x, int v) {
	v += z;
	d[v] = {x, 1, 0, 1, x};
	v /= 2;
	while (v > 0) {
		d[v].lewy = d[2 * v].lewy;
		d[v].prawy = d[2 * v + 1].prawy;
		if (d[2 * v].prawy < d[2 * v + 1].lewy) {
			if (d[2 * v].pref == d[2 * v].suf) d[v].pref = d[2 * v].suf + d[2 * v + 1].pref;
			else d[v].pref = d[2 * v].pref;

			if (d[2 * v + 1].pref == d[2 * v + 1].suf) d[v].suf = d[2 * v].suf + d[2 * v + 1].pref;
			else d[v].suf = d[2 * v + 1].suf;


			if (d[2 * v].pref != d[2 * v].suf && d[2 * v + 1].pref != d[2 * v + 1].suf) d[v].sr = max(max(d[2 * v].sr, d[2 * v + 1].sr), d[2 * v].suf + d[2 * v + 1].pref);
			else if (d[2 * v + 1].pref != d[2 * v + 1].suf) d[v].sr = d[2 * v + 1].sr;
			else if (d[2 * v].pref != d[2 * v].suf) d[v].sr = d[2 * v].sr;
		} else {
			d[v].pref = d[2 * v].pref;
			d[v].suf = d[2 * v + 1].suf;
			if (d[2 * v].pref != d[2 * v].suf && d[2 * v + 1].pref != d[2 * v + 1].suf) d[v].sr = max(max(d[2 * v].sr, d[2 * v + 1].sr), max(d[2 * v].suf, d[2 * v + 1].pref));
			else if (d[2 * v].pref != d[2 * v].suf) d[v].sr = max(d[2 * v].sr, d[2 * v].suf);
			else if (d[2 * v + 1].pref != d[2 * v + 1].suf) d[v].sr = max(d[2 * v + 1].sr, d[2 * v + 1].pref);
		}
		v /= 2;
	}
}

void show() {
	int pp = 1;
	for (int v = 1; v < 2 * z; v++) {
		printf("(%d|%d,%d,%d)", v, d[v].pref, d[v].sr, d[v].suf);
		if (v == pp) {
			pp = 2 * pp + 1;
			printf("\n");
		}
	}
	printf("\n");
}

int main() {
	scanf("%d", &n);
	//for (int i = 0; i < z; i++) wstaw(1000, i);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		wstaw(x, i);
	}
	scanf("%d", &m);
	show();
	printf("%d\n", max(max(d[1].pref, d[1].sr), d[1].suf));
	for (int i = 0; i < m; i++) {
		int v, x;
		scanf("%d%d", &v, &x);
		wstaw(x, v - 1);
		show();
		printf("%d\n", max(max(d[1].pref, d[1].sr), d[1].suf));
		printf("%d, %d, %d\n", d[1].pref, d[1].sr, d[1].suf);
	}

}
/* 8
4 2 3 1 4 1 2 3
1
2 2
*/