赛时忘记用 set 了，用的权值线段树。其他都对，但是 hack 数据0102 WA 了

#include <bits/stdc++.h>

using namespace std;

int n, q;
int a[200005];

struct SegmentTree {
	int sz;
	vector<int> val;
	int ide = 0;
	
	void pushup(int x) {
		val[x] = min(val[x * 2], val[x * 2 + 1]);
	}
	SegmentTree(){}
	SegmentTree(int n) {
		for (sz = 1; sz < n; sz *= 2);
		val.assign(2 * sz, ide);
	}
	void mdf(int x, int lx, int rx, int p, int v) {
		if (lx + 1 == rx) {
			val[x] += v;
//			printf("!%d:%d\n", p, val[x]);
			return ;
		}
		int m = (lx + rx) / 2;
		if (p < m)
			mdf(x * 2, lx, m, p, v);
		else
			mdf(x * 2 + 1, m, rx, p, v);
		pushup(x);
	}
	int qry(int x, int lx, int rx) {
//		printf("%d:[%d,%d)\n", lx, rx);
		if (lx + 1 == rx)
			return lx;
		int m = (lx + rx) / 2;
		if (val[x * 2] == 0)
			return qry(x * 2, lx, m);
		return qry(x * 2 + 1, m, rx);
	}
	int qry2(int x, int lx, int rx, int p) {
//		printf("%d:[%d,%d) %d\n", x, lx, rx, p); 
		if (lx + 1 == rx)
			return val[x];
		int m = (lx + rx) / 2;
		if (p < m)
			return qry2(x * 2, lx, m, p);
		return qry2(x * 2 + 1, m, rx, p);
	}
} st;

int ans;

int main() {
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	st = SegmentTree(n + 100);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i]++;
		st.mdf(1, 1, st.sz + 1, a[i], 1);
	}
	
	for (int i = 1; i <= q; i++) {
		int p, v;
		cin >> p >> v;
		v++;
		st.mdf(1, 1, st.sz + 1, a[p], -1);
		if (v <= n + 10)
			st.mdf(1, 1, st.sz + 1, v, 1);
//		cout << st.qry2(1, 1, st.sz + 1, a[p]) << endl;
		a[p] = v;
		
		cout << st.qry(1, 1, st.sz + 1) - 1 << endl;
	}
	return 0;
}