0分求调，玄2关

#include<bits/stdc++.h>
using namespace std;
int rt,m,q,op,tmp,cnt;
struct str{
    int l,r,v,sz;
}t[500005];
int find(int x,int val)
{
    if(x==0) return 0;
    if(val<t[x].v) return find(t[x].l,val);
    else if(val>t[x].v) return find(t[x].r,val)+t[t[x].l].sz+1;
    return t[t[x].l].sz+1;
}
void update(int x){t[x].sz=t[t[x].l].sz+t[t[x].r].sz+1;}
void lot(int &x)
{
    int y=t[x].r;
    t[x].r=t[y].l;
    t[y].l=x;
    update(x);
    update(y);
    x=y;
    return ;
}
void rot(int &x)
{
    int y=t[x].l;
    t[x].l=t[y].r;
    t[y].r=x;
    update(x);
    update(y);
    x=y;
    return ;
}
void splay(int &x,int val)
{
    if(x==0||val<1||val>t[x].sz) return ;
    if(val<=t[t[x].l].sz)
    {
        if(val<=t[t[t[x].l].l].sz)
        {
            splay(t[t[x].l].l,val);
            rot(x);
            rot(x);
        }
        else if(val>t[t[t[x].l].l].sz+1)
        {
            splay(t[t[x].l].r,val-t[t[t[x].l].l].sz-1);
            lot(t[x].l);
            rot(x);
        }
        else rot(x);
    }
    else if(val>t[t[x].l].sz+1)
    {
        int rv=val-t[t[t[x].l].l].sz-1;
        if(rv<=t[t[t[x].r].l].sz)
        {
            splay(t[t[x].r].l,rv);
            rot(t[x].r);
            lot(x);
        }
        else if(rv>t[t[t[x].r].l].sz+1)
        {
            splay(t[t[x].r].r,rv-t[t[t[x].r].l].sz-1);
            lot(x);
            lot(x);
        }
        else lot(x);
    }
    update(x);
    return ;
}
int hb(int x,int y)
{
    if(x==0) return y;
    if(y==0) return x;
    splay(x,t[x].sz);
    t[x].r=y;
    update(x);
    return x;
}
void cf(int x,int val,int &l,int &r)
{
    if(x==0)
    {
        l=r=0;
        return ;
    }
    if(val<=t[t[x].l].sz)
    {
        cf(t[x].l,val,l,t[x].l);
        x=r;
    }
    else
    {
        cf(t[x].r,val-t[t[x].l].sz-1,t[x].r,r);
        x=l;
    }
    update(x);
    return ;
}
void add(int val)
{
    int x=rt,res=0;
    while(x)
    {
        if(t[x].v<val)
        {
            res+=t[t[x].l].sz+1;
            x=t[x].r;
        }
        else x=t[x].l;
    }
    int ll=0,rr=0;
    cf(rt,res,ll,rr);
    t[++cnt]={0,0,val,1};
    rt=hb(hb(ll,cnt),rr);
    return ;
}
int finds(int val)
{
    int x=rt;
    while(x)
    {
        if(val==t[t[x].l].sz+1) break;
        else if(val<=t[t[x].l].sz) x=t[x].l;
        else 
        {
            val-=t[t[x].l].sz+1;
            x=t[x].r;
        }
    }
    splay(rt,find(rt,t[x].v));
    return t[x].v;
}
int main()
{
    scanf("%d%d",&m,&q);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&tmp);
        add(tmp);
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&op,&tmp);
        if(op==1) printf("%d\n",finds(cnt-tmp+1));
        else if(op==2) add(tmp);
    }
    return 0;
}