P3369

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int cnt=0;
struct node{
	int lson,rson;//左右儿子 
	int key,prio;//键值 优先级 
	int siz;//子树节点数量 
}treap[M];
void Newnode(int x){
	cnt++;
	treap[cnt]=(node){0,0,x,rand(),1};
}
void Up(int u){
	treap[u].siz=treap[treap[u].lson].siz+treap[treap[u].rson].siz+1; 
}
void LeftRotate(int &u){
	int k=treap[u].rson;
	treap[u].rson=treap[k].lson;
	treap[k].lson=u;
	treap[k].siz=treap[u].siz;
	Up(u);u=k;
}
void RightRotate(int &u){
	int k=treap[u].lson;
	treap[u].lson=treap[u].rson;
	treap[k].rson=u;
	treap[k].siz=treap[u].siz;
	Up(u);u=k;
}
void Insert(int &u,int x){
	if(u==0){Newnode(x);u=cnt;return;}
	treap[u].siz++;
	if(x>=treap[u].key) Insert(treap[u].rson,x);
	else Insert(treap[u].lson,x);
	if(treap[u].lson!=0&&treap[u].prio>treap[treap[u].lson].prio) RightRotate(u);
	if(treap[u].rson!=0&&treap[u].prio>treap[treap[u].rson].prio) LeftRotate(u);
	Up(u);
}
void Delete(int &u,int x){
	treap[u].siz--;
	if(treap[u].key==x){
		if(treap[u].lson==0&&treap[u].rson==0){u=0;return;}
		if(treap[u].lson==0||treap[u].rson==0){u=treap[u].lson+treap[u].rson;return;}
		if(treap[treap[u].lson].prio<treap[treap[u].rson].prio){
			RightRotate(u);Delete(treap[u].rson,x);return;
		}
		else{LeftRotate(u);Delete(treap[u].lson,x);return;}
	}
	if(treap[u].key>=x) Delete(treap[u].lson,x);
	else Delete(treap[u].rson,x);
	Up(u); 
}
int Rank(int u,int x){
	if(u==0) return 0;
	if(x>treap[u].key) return treap[treap[u].lson].siz+1+Rank(treap[u].rson,x);
	return Rank(treap[u].lson,x);
}
int Kth(int u,int k){
	if(k==treap[treap[u].lson].siz+1) return treap[u].key;
	if(k>treap[treap[u].lson].siz+1) return Kth(treap[u].rson,k-treap[treap[u].lson].siz-1);
	if(k<=treap[treap[u].lson].siz) Kth(treap[u].lson,k);
}
int Precursor(int u,int x){
	if(u==0) return 0;
	if(treap[u].key>=x) return Precursor(treap[u].lson,x);
	int temp=Precursor(treap[u].rson,x);
	if(temp==0) return treap[u].key;
	return temp;
}
int Successor(int u,int x){
	if(u==0) return 0;
	if(treap[u].key<=x) return Successor(treap[u].rson,x);
	int temp=Successor(treap[u].lson,x);
	if(temp==0) return treap[u].key;
	return temp;
}
int main(){
	srand(time(NULL));
	int root=0;
	int n;scanf("%d",&n);
	while(n--){
		int op,x;
		scanf("%d%d",&op,&x);
		switch(op){
			case 1:Insert(root,x);break;
			case 2:Delete(root,x);break;
			case 3:printf("%d\n",Rank(root,x)+1);break;
			case 4:printf("%d\n",Kth(root,x));break;
			case 5:printf("%d\n",Precursor(root,x));break;
			case 6:printf("%d\n",Successor(root,x));break; 
		}
	}
	return 0;
}