#include <bits/stdc++.h>
using namespace std;
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
const int N = 200025, M = 200020, inf = 0x3f3f3f3f;
int n, Q;
int a[N], cnt[N];
struct Segment_Tree {
	int L1[N*4], R1[N*4], L0[N*4]; //区间最左边的1，最右边的1，最左边的0
	int tag[N*4];
	
	void pushup(int p) {
		L1[p] = min(L1[ls(p)], L1[rs(p)]);
		R1[p] = max(R1[ls(p)], R1[rs(p)]);
		L0[p] = min(L0[ls(p)], L0[rs(p)]);
	}
	
	void apply(int p, int l, int r, int v) {
		if (v == 0) L1[p] = inf, R1[p] = -inf, L0[p] = l;
		else L1[p] = l, R1[p] = r, L0[p] = inf;
	}
	
	void pushdown(int p, int l, int r) {
		if (~tag[p]) {
			int mid = l + r >> 1;
			apply(ls(p), l, mid, tag[p]), apply(rs(p), mid + 1, r, tag[p]);
			tag[p] = -1;
		}
	}
	
	void build(int p, int l, int r) {
		tag[p] = -1;
		if (l == r) {
			if (cnt[l]) L1[p] = R1[p] = l, L0[p] = inf;
			else L1[p] = inf, R1[p] = -inf, L0[p] = l;
			return;
		}
		int mid = l + r >> 1;
		build(ls(p), l, mid), build(rs(p), mid + 1, r);
		pushup(p);
	}
	
	void change(int p, int l, int r, int x, int y, int v) {
		if (x <= l && r <= y) {
			tag[p] = v;
			apply(p, l, r, v);
			return;
		}
		pushdown(p, l, r);
		int mid = l + r >> 1;
		if (x <= mid) change(ls(p), l, mid, x, y, v);
		if (y > mid) change(rs(p), mid + 1, r, x, y, v);
		pushup(p);
	}
	
	int queryL1(int p, int l, int r, int x, int y) {
		if (x <= l && r <= y) return L1[p];
		pushdown(p, l, r);
		int mid = l + r >> 1, res = inf;
		if (x <= mid) res = min(res, queryL1(ls(p), l, mid, x, y));
		if (y > mid) res = min(res, queryL1(rs(p), mid + 1, r, x, y));
		return res;
	}
	
	int queryL0(int p, int l, int r, int x, int y) {
		if (x <= l && r <= y) return L0[p];
		pushdown(p, l, r);
		int mid = l + r >> 1, res = inf;
		if (x <= mid) res = min(res, queryL0(ls(p), l, mid, x, y));
		if (y > mid) res = min(res, queryL0(rs(p), mid + 1, r, x, y));
		return res;
	}
} sTr;

int main() {
	scanf("%d%d", &n, &Q);
	for (int i = 1, x; i <= n; ++i) scanf("%d", &x), ++cnt[x], a[i] = x;
	for (int i = 1; i <= M; ++i) cnt[i + 1] += cnt[i] / 2, cnt[i] &= 1;
	sTr.build(1, 1, M);
	while (Q--) {
		int x, y; scanf("%d%d", &x, &y);
		int L1 = sTr.queryL1(1, 1, M, a[x], M);
		if (a[x] < L1) sTr.change(1, 1, M, a[x], L1 - 1, 1); sTr.change(1, 1, M, L1, L1, 0);
		a[x] = y;
		int L0 = sTr.queryL0(1, 1, M, a[x], M);
		if (a[x] < L0) sTr.change(1, 1, M, a[x], L0 - 1, 0); sTr.change(1, 1, M, L0, L0, 1);
		printf("%d\n", sTr.R1[1]);
	}
	return 0;
}