最后一个测试点中间输出了0，其他都是对的

#include <cstdio>
#include <algorithm>
#include <ctype.h>
#define ll long long
using namespace std;
const int maxn = 1e7+5;
int n , m , cnt , rt , ls[maxn<<1] , rs[maxn<<1] , tot , num , no;
ll sum[maxn<<1] , a[maxn] , c[maxn] , q[maxn] , d[maxn] , op[maxn] , b[maxn];
inline ll input()
{
	char ch=getchar();int x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
inline void print(ll x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+48);
}
inline void PushUp(int p){sum[p]=sum[ls[p]]+sum[rs[p]];}
void Insert(int &p , int l , int r , int val)
{
	if (!p) p=++cnt;
	if (l == r){sum[p]++;return;}
	int mid = l + r >> 1;
	if (val <= mid) Insert(ls[p] , l , mid , val);
	else Insert(rs[p] , mid + 1 , r , val);
	PushUp(p);
	return;
}
ll Query(int &p , int l , int r , int k)
{
	if (!p)return 0;
	if (l == r)return l;
	int mid = l + r >> 1;
	if (k <= sum[rs[p]])return Query(rs[p] , mid + 1 , r , k);
	else return Query(ls[p] , l , mid , k - sum[rs[p]]);
}
int main ()
{
	//freopen("in.txt" , "r" , stdin);
	n=input() , m=input();
	for (int i = 1; i <= n; ++i){int x=input();a[++tot]=d[i]=x;}
	for (int i = 1; i <= m; ++i)
	{
		op[i]=input() , c[i]=input();
		if (op[i] == 1) a[++tot]=c[i];
	}
	sort(a + 1 , a + tot + 1);
	a[0]=-2147483647;
	for (int i = 1; i <= tot; i++)if(a[i] != a[i - 1])b[++num]=a[i];
	for (int i = 1; i <= n; ++i)Insert(rt , 1 , maxn , lower_bound(b + 1 , b + num + 1 , d[i])-b);
	for (int i = 1; i <= m; ++i)
	{
		if (op[i] == 1)Insert(rt , 1 , maxn , lower_bound(b + 1 , b + num + 1 , c[i])-b);
		else print(b[Query(rt , 1 , maxn , c[i])]),putchar('\n');
	}
	return 0;
}