#pragma GCC optimize(3,"Ofast","inline") #pragma GCC optimize(2) #include #include #include #include #define Re register int #define pl tr[p].lp #define pr tr[p].rp #define pv tr[p].v using namespace std; const int N=1e5+5,inf=2e9; int a,b,o,T,root; inline void in(Re &x){ int fu=0;x=0;char c=getchar(); while(c<'0'||c>'9')fu|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=fu?-x:x; } struct Treap{int v,rd,lp,rp,cnt,size;}tr[N]; inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;} inline void lturn(Re &p){ Re q=pr;pr=tr[q].lp,tr[q].lp=p; pushup(p),pushup(p=q); } inline void rturn(Re &p){ Re q=pl;pl=tr[q].rp,tr[q].rp=p; pushup(p),pushup(p=q); } inline void insert(Re &p,Re x){ if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;} ++tr[p].size; if(x==pv)++tr[p].cnt; else if(xpv)--tr[p].size,del(pr,x); else{ if(tr[p].cnt>1)--tr[p].cnt,--tr[p].size; else{ if(pl*pr==0)p=pl+pr; else if(tr[pl].rd=pv)return ask_nex(pr,x); else return min(pv,ask_nex(pl,x)); } int main(){ srand((int)time(NULL)); in(T); while(T--){ in(a),in(b); if(a==1)insert(root,b); if(a==2)del(root,b); if(a==3)printf("%d\n",ask_level(root,b)); if(a==4)printf("%d\n",ask_v(root,b)); if(a==5)printf("%d\n",ask_pri(root,b)); if(a==6)printf("%d\n",ask_nex(root,b)); } }