treap

#include<bits/stdc++.h>
#include<random>
using namespace std;
typedef long long ll;
const ll MAXN=3e5+5;
ll n,op,x;
struct node{
	ll lson,rson;
	ll val,pri,sz;
};
node treap[MAXN];
ll tot,root;
void new_node(ll num){
	tot++;
	treap[tot].lson=treap[tot].rson=0;
	treap[tot].val=num,treap[tot].sz=1;
	treap[tot].pri=rand();
	return;
}
void update(ll now){
	treap[now].sz=treap[treap[now].lson].sz+treap[treap[now].rson].sz+1;
	return;
}
void split(ll now,ll num,ll &L,ll &R){
	if(now==0){
		L=0;
		R=0;
		return;
	}
	if(treap[now].val<=num){
		L=now;
		split(treap[now].rson,num,treap[now].rson,R);
	}
	else{
		R=now;
		split(treap[now].lson,num,L,treap[now].lson);
	}
	update(now);
	return;
}
ll merge(ll L,ll R){
	if(L==0||R==0)return L+R;
	if(treap[L].pri>treap[R].pri){
		treap[L].rson=merge(treap[L].rson,R);
		update(L);
		return L;
	}
	else{
		treap[R].lson=merge(L,treap[R].lson);
		update(R);
		return R;
	}
}
ll insert(ll num){
	ll L,R;
	split(root,num,L,R);
	new_node(num);
	root=merge(merge(L,tot),R);
	return tot;
}
ll del(ll num){
	ll L,M,R;
	split(root,num,L,R);
	split(L,num-1,L,M);
	M=merge(treap[M].lson,treap[M].rson);
	root=merge(merge(L,M),R);
	return root;
}
ll rk(ll num){
	ll L,R,res;
	split(root,num-1,L,R);
	res=treap[L].sz+1;
	root=merge(L,R);
	return res;
}
ll kth(ll now,ll num){
	if(treap[treap[now].lson].sz+1==num)return now;
	if(treap[treap[now].lson].sz>=num)return kth(treap[now].lson,num);
	return kth(treap[now].rson,num-(treap[treap[now].lson].sz+1));
}
ll pre(ll num){
	ll L,R,res;
	split(root,num-1,L,R);
	res=treap[kth(L,treap[L].sz)].val;
	root=merge(L,R);
	return res;
}
ll nxt(ll num){
	ll L,R,res;
	split(root,num,L,R);
	res=treap[kth(R,1)].val;
	root=merge(L,R);
	return res;
}
int main(){
	srand(time(NULL));
	cin>>n;
	while(n--){
		cin>>op;
		if(op==1){
			cin>>x;
			insert(x);
		}
		else if(op==2){
			cin>>x;
			del(x);
		}
		else if(op==3){
			cin>>x;
			cout<<rk(x)<<'\n';
		}
		else if(op==4){
			cin>>x;
			cout<<kth(root,x)<<'\n';
		}
		else if(op==5){
			cin>>x;
			cout<<pre(x)<<'\n';
		}
		else{
			cin>>x;
			cout<<nxt(x)<<'\n';
		}
	}
	return 0;
}