#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int n, q, a[1000005];
int c[1000005];
multiset<int> pos[1000005];
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
int O(int x) {
	int t = s.order_of_key(x);
	if (*(s.find_by_order(t)) == x) return t + 1;
	return t;
}
struct Seg {
	struct Dat {
		int u, w;
		Dat operator+(const Dat &b) const {
			if (w <= b.w) return *this;
			return b;
		}
	} f[4000005];
	int tg[4000005];
	void Pushtag(int p, int w) {
		f[p].w += w, tg[p] += w;
	}
	void Pushdown(int p) {
		if (tg[p]) {
			Pushtag(p << 1, tg[p]), Pushtag(p << 1 | 1, tg[p]);
			tg[p] = 0;
		}
	}
	void Build(int p, int l, int r) {
		f[p].w = inf, f[p].u = l;
		if (l == r) return;
		int mid = l + r >> 1;
		Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r);
	}
	void ModifyP(int p, int l, int r, int i, int w) {
		if (l == r) return void(f[p].w = w);
		int mid = l + r >> 1;
		Pushdown(p);
		if (i <= mid) ModifyP(p << 1, l, mid, i, w);
		else ModifyP(p << 1 | 1, mid + 1, r, i, w);
		f[p] = f[p << 1] + f[p << 1 | 1];
	}
} fS, gS;
void Modify(int p, int l, int r, int L, int R, int w) {
	if (l >= L && r <= R) {
		fS.Pushtag(p, w), gS.Pushtag(p, -w);
		return;
	}
	if (l > R || r < L) return;
	int mid = l + r >> 1;
	fS.Pushdown(p), gS.Pushdown(p);
	Modify(p << 1, l, mid, L, R, w), Modify(p << 1 | 1, mid + 1, r, L, R, w);
	fS.f[p] = fS.f[p << 1] + fS.f[p << 1 | 1];
	gS.f[p] = gS.f[p << 1] + gS.f[p << 1 | 1];
}
void UpdF(int w) {
	if (s.find(w) != s.end()) {
		fS.ModifyP(1, 1, n, w, inf);
		return;
	}
	if (pos[w].size()) fS.ModifyP(1, 1, n, w, O(w) - c[*pos[w].begin()]);
	else fS.ModifyP(1, 1, n, w, -inf);
}
void UpdG(int w) {
	if (s.find(w) == s.end()) {
		gS.ModifyP(1, 1, n, w, inf);
		return;
	}
	if (pos[w].size()) gS.ModifyP(1, 1, n, w, c[*pos[w].begin()] - O(w));
	else gS.ModifyP(1, 1, n, w, inf);
}
void Upd() {
	while (true) {
		if (fS.f[1].w < 0) {
			int i = fS.f[1].u;
			s.insert(i);
			UpdF(i), UpdG(i);
			Modify(1, 1, n, i + 1, n, 1);
			continue;
		}
		if (gS.f[1].w < 0) {
			int i = gS.f[1].u;
			s.erase(i);
			UpdF(i), UpdG(i);
			Modify(1, 1, n, i + 1, n, -1);
			continue;
		}
		break;
	}
}
void Ins(int p, int w) {
	if (w == -1) return;
	pos[w].insert(p);
	UpdF(w), UpdG(w);
}
void Del(int p, int w) {
	if (w == -1) return;
	pos[w].erase(pos[w].find(p));
	UpdF(w), UpdG(w);
}
int main() {
	scanf("%d%d", &n, &q);
	fS.Build(1, 1, n), gS.Build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		if (!a[i]) c[i] = 1;
	}
	for (int i = 1; i <= n; i++) c[i] += c[i - 1];
	for (int i = 1; i <= n; i++) s.insert(i);
	while (q--) {
		int x, k, y; scanf("%d%d%d", &x, &k, &y);
		Del(x, a[x]), Ins(x, a[x] = k), Upd();
		if (a[y]) printf("%d\n", a[y]);
		else printf("%d\n", *(s.find_by_order(c[y] - 1)));
	}
	return 0;
}