#include<bits/stdc++.h>

using namespace std;

const int maxn = 1000010;

int m, q;

class Splay
{
	int root, tot;
	struct node
	{
		int father, son[2];
		int val, size, cnt;
	}t[maxn];
	inline void update(int x)
	{
		t[x].size = t[t[x].son[0]].size + t[t[x].son[1]].size + t[x].cnt;
	}
	inline bool get(int x)
	{
		return x == t[t[x].father].son[1];
	}
	void rotate(int x)
	{
		int y = t[x].father;
		int z = t[y].father;
		int chk = get(x);
		if(z) t[z].son[get(y)] = x;
		t[x].father = z;
		t[y].son[chk] = t[x].son[chk ^ 1];
		t[t[x].son[chk ^ 1]].father = y;
		t[x].son[chk ^ 1] = y;
		t[y].father = x;
		update(y);
		update(x);
	}
	void splay(int x, int goal)
	{
		for(;t[x].father ^ goal; rotate(x))
		{
			int y = t[x].father;
			int z = t[y].father;
			if(z ^ goal) (get(x) == get(y))? rotate(y): rotate(x);
		}
		if(!goal) root = x;
	}

public:
	void insert(int k)
	{
		int x = root;
		int fa = 0;
		while(k ^ t[x].val && x)//
		{
			fa = x;
			x = t[fa].son[k > t[x].val];
		}
		if(x) t[x].cnt++;
		else
		{
			x = ++tot;
			if(fa) t[fa].son[k > t[fa].val] = x;
			t[x].father = fa;
			t[x].size = t[x].cnt = 1;
			t[x].son[0] = t[x].son[1] = 0;
			t[x].val = k;
		}
		splay(tot, 0);//就是这里，现在交上去只能得10分，但是把tot改为x就AC了 
	}//这两个数有区别吗 
	int kth(int k)
	{
		int x = root;
		if(k > t[x].size) return 0;
		while(1)
		{
			int y = t[x].son[0];
			if(k > t[x].cnt + t[y].size)
			{
				k -= t[x].cnt + t[y].size;
				x = t[x].son[1];
			}
			else if(k <= t[y].size) x = y;
			else return t[x].val;
		}	
	}
};
Splay tree;

signed main()
{
	scanf("%d%d", &m, &q);
	int c, x;
	for(int i = 1; i <= m; i++)
	{
		scanf("%d", &x);
		tree.insert(x);
	}
	for(int i = 1; i <= q; i++)
	{
		scanf("%d%d", &c, &x);
		if(c == 1)
		{
			printf("%d\n",tree.kth(m - x + 1));
		}
		else
		{
			tree.insert(x);
			m++;
		}
	}
	return 0;
}