//#pragma GCC optimize(3,"Ofast","inline") //#pragma GCC optimize(2) #include #include #define Re register int #define pl tr[p].ps[0] #define pr tr[p].ps[1] #define pf tr[p].fa #define pv tr[p].v using namespace std; const int N=1e5+5,inf=2e9; int T,a,b,n,o,root; struct Splay{int v,fa,ps[2],cnt,size;}tr[N]; 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; } inline void pushup(Re p){if(!p)return;/*�������Ҫ���ж�return����������*/tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;} inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;} inline int which(Re p){return tr[pf].ps[1]==p;} inline void rotate(Re p){ Re y=pf,ys=which(p); Re R=tr[y].fa,Rs=which(y); Re B=tr[p].ps[ys^1]; connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs); pushup(y),pushup(p); } inline void Splay(Re p){ for(Re fa;fa=pf;rotate(p)) if(tr[fa].fa)rotate(which(p)==which(fa)?fa:p); root=p; } inline void New(Re x,Re fa){ tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1; if(fa)tr[fa].ps[tr[fa].v1){--tr[p].cnt,--tr[p].size;return;} if(!pl&&!pr){root=0;return;} if(!pl||!pr){tr[root=pl+pr].fa=0;return;} Splay(ask_pri_p(root)); tr[root].ps[1]=pr,tr[pr].fa=root; pushup(root); } int main(){ in(T); while(T--){ in(a),in(b); if(a==1)insert(b); if(a==2)del(b); if(a==3)printf("%d\n",ask_level(root,b)); if(a==4)printf("%d\n",ask_v(root,b)); if(a==5)insert(b),printf("%d\n",tr[ask_pri_p(root)].v),del(b); if(a==6)insert(b),printf("%d\n",tr[ask_nex_p(root)].v),del(b); } }