用 fhq_Treap 做的，然后就 T 了……

#include <bits/stdc++.h>

using namespace std;

const int N = 1000000 + 5;

struct tree {
	int l, r, pty, val, sz;
} node[N]; 

int n, num, root, dl, dr, m;

void pushup(int x) {
	node[x].sz = node[node[x].l].sz + node[node[x].r].sz + 1;
	return;
}

void split(int u, int & l, int & r, int val) {
	if (!u) {
		l = r = 0;
		return;
	} 
	if (node[u].val <= val) {
		l = u;
		split(node[u].r, node[u].r, r, val);
	} else {
		r = u;
		split(node[u].l, l, node[u].l, val);
	}
	pushup(u);
	return;
}

void add(int val) {
	num++;
	node[num].val = val;
	node[num].sz = 1;
	node[num].pty = rand();
	node[num].l = 0;
	node[num].r = 0;
	return;
}

int merge(int l, int r) {
	if (!l || !r) {
		return l + r;
	}
	if (node[l].pty <= node[r].pty) {
		node[l].r = merge(node[l].r, r);
		pushup(l);
		return l;
	} else {
		node[r].l = merge(l, node[r].l);
		pushup(r);
		return r;
	}
}

int kth(int u, int p) {
	if (p <= node[node[u].l].sz && node[u].l) {
		return kth(node[u].l, p);
	} else if (p == node[node[u].l].sz + 1) {
		return u;
	} else {
		p -= node[node[u].l].sz + 1;
		if (node[u].r && p) {
			return kth(node[u].r, p);
		}
	}
}

int main(void) {
	cin >> n >> m;
	srand(time(NULL));
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		split(root, dl, dr, x);
		add(x);
		root = merge(merge(dl, num), dr);
	}
	int opt, x;
	for (int i = 1; i <= m; i++) {
		cin >> opt >> x;
		if (opt == 2){
			split(root, dl, dr, x);
			add(x);
			root = merge(merge(dl, num), dr);
		} else {
			cout << node[kth(root, n - x + 1)].val << endl;
		}
	} 
	return 0;
}