1 //OJ 1999  2 //by Cydiater  3 //2016.8.30  4 #include <iostream>  5 #include <cstdio>  6 #include <cstdlib>  7 #include <string>  8 #include <queue>  9 #include <map> 10 #include <ctime> 11 #include <cmath> 12 #include <algorithm> 13 #include <string>                                                                 14 #include <iomanip> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)    for(int i=j;i<=n;i++) 18 #define down(i,j,n)    for(int i=j;i>=n;i--) 19 const int MAXN=1e5+5; 20 const int oo=0x3f3f3f3f; 21 inline ll read(){ 22     char ch=getchar();ll x=0,f=1; 23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 int N,op,num,root=0,tol=0,ans=0; 28 struct node{ 29     int leftt,rightt,v,cnt,rnd,siz; 30 }t[MAXN]; 31 namespace solution{ 32     void updata(int k){ 33         t[k].siz=t[t[k].leftt].siz+t[t[k].rightt].siz+t[k].cnt; 34     } 35     void lefturn(int &k){ 36         int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k; 37         t[tt].siz=t[k].siz;updata(k);k=tt; 38     } 39     void righturn(int &k){ 40         int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k; 41         t[tt].siz=t[k].siz;updata(k);k=tt; 42     } 43     void insert(int &k,int x){ 44         if(k==0){ 45             tol++;k=tol;t[k].siz=t[k].cnt=1; 46             t[k].v=x;t[k].rnd=rand(); 47             return; 48         } 49         t[k].siz++; 50         if(t[k].v==x)        t[k].cnt++; 51         else if(x>t[k].v){ 52             insert(t[k].rightt,x); 53             if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k); 54         }else{ 55             insert(t[k].leftt,x); 56             if(t[t[k].leftt].rnd<t[k].rnd)righturn(k); 57         } 58     } 59     void del(int &k,int x){ 60         if(k==0)    return; 61         if(t[k].v==x){ 62             if(t[k].cnt>1){t[k].cnt--;t[k].siz--;return;} 63             if(t[k].leftt*t[k].rightt==0)k=t[k].leftt+t[k].rightt; 64             else if(t[t[k].leftt].rnd<t[t[k].rightt].rnd){ 65                 righturn(k);del(k,x); 66             }else{ 67                 lefturn(k);del(k,x); 68             } 69         }else if(x>t[k].v){ 70             t[k].siz--; 71             del(t[k].rightt,x); 72         }else{ 73             t[k].siz--; 74             del(t[k].leftt,x); 75         } 76     } 77     int query_rank(int k,int x){ 78         if(k==0)return 0; 79         if(t[k].v==x)        return t[t[k].leftt].siz+1; 80         else if(x>t[k].v)    return t[t[k].leftt].siz+t[k].cnt+query_rank(t[k].rightt,x); 81         else                 return query_rank(t[k].leftt,x); 82     } 83     int query_num(int k,int x){ 84         if(k==0)                                return 0; 85         if(x<=t[t[k].leftt].siz)                return query_num(t[k].leftt,x); 86         else if(x>t[t[k].leftt].siz+t[k].cnt)    return query_num(t[k].rightt,x-(t[t[k].leftt].siz+t[k].cnt)); 87         else                                     return t[k].v; 88     } 89     void query_pre(int k,int x){ 90         if(k==0)        return; 91         if(t[k].v<x){ 92             ans=t[k].v; 93             query_pre(t[k].rightt,x); 94         }else query_pre(t[k].leftt,x); 95     } 96     void query_nxt(int k,int x){ 97         if(k==0)        return; 98         if(t[k].v>x){ 99             ans=t[k].v;100             query_nxt(t[k].leftt,x);101         }else query_nxt(t[k].rightt,x);102     }103     void slove(){104         N=read();105         up(i,1,N){106             op=read();num=read();107             if(op==1)insert(root,num);108             if(op==2)del(root,num);109             if(op==3)printf("%d\n",query_rank(root,num));110             if(op==4)printf("%d\n",query_num(root,num));111             if(op==5){112                 query_pre(root,num);113                 printf("%d\n",ans);114             }115             if(op==6){116                 query_nxt(root,num);117                 printf("%d\n",ans);118             }119         }120     }121 }122 int main(){123     //freopen("input.in","r",stdin);124     using namespace solution;125     slove();    126     return 0;127 }