1 //SPOJ 3273  2 //by Cydiater  3 //2016.8.31  4 #include <iostream>  5 #include <cstring>  6 #include <ctime>  7 #include <cmath>  8 #include <cstdlib>  9 #include <string> 10 #include <algorithm> 11 #include <queue> 12 #include <map> 13 #include <iomanip> 14 #include <cstdio> 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=1e6+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22     char ch=getchar();int 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,num,root=0,tol=0; 28 char op; 29 map<int,int>m; 30 struct node{ 31     int rnd,v,cnt,siz,leftt,rightt; 32 }t[MAXN]; 33 namespace solution{ 34     void updata(int k){ 35         t[k].siz=t[t[k].leftt].siz+t[t[k].rightt].siz+t[k].cnt; 36     } 37     void lefturn(int &k){ 38         int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k; 39         t[tt].siz=t[k].siz;updata(k);k=tt; 40     } 41     void righturn(int &k){ 42         int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k; 43         t[tt].siz=t[k].siz;updata(k);k=tt; 44     } 45     void insert(int &k,int x){ 46         if(k==0){ 47             k=++tol;t[k].leftt=t[k].rightt=0; 48             t[k].cnt=1;t[k].siz=1;t[k].v=x; 49             t[k].rnd=rand(); 50             return; 51         } 52         t[k].siz++; 53         if(t[k].v==x)t[k].cnt++; 54         else if(x>t[k].v){ 55             insert(t[k].rightt,x); 56             if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k); 57         }else if(x<t[k].v){ 58             insert(t[k].leftt,x); 59             if(t[t[k].leftt].rnd<t[k].rnd)righturn(k); 60         } 61     } 62     void del(int &k,int x){ 63         if(k==0)    return; 64         if(x==t[k].v){ 65             if(t[k].cnt>1){t[k].siz--;t[k].cnt--;return;} 66             else if(t[k].leftt*t[k].rightt==0)    k=t[k].leftt+t[k].rightt; 67             else if(t[t[k].leftt].rnd<t[t[k].rightt].rnd){ 68                 righturn(k); 69                 del(k,x); 70             } 71             else if(t[t[k].leftt].rnd>t[t[k].rightt].rnd){ 72                 lefturn(k); 73                 del(k,x); 74             } 75         }else if(x>t[k].v){ 76             t[k].siz--; 77             del(t[k].rightt,x); 78         }else if(x<t[k].v){ 79             t[k].siz--; 80             del(t[k].leftt,x); 81         } 82     } 83     int query_num(int k,int x){ 84         if(k==0)                                return oo; 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     int query_siz(int k,int x){ 90         if(k==0)                                return 0; 91         if(x<=t[k].v)                            return query_siz(t[k].leftt,x); 92         else if(x>t[k].v)                        return t[t[k].leftt].siz+t[k].cnt+query_siz(t[k].rightt,x); 93     } 94     void slove(){ 95         N=read(); 96         while(N--){ 97             scanf("%c",&op);num=read(); 98             if(op==‘I‘)if(m[num]==0){insert(root,num);m[num]=1;} 99             if(op==‘D‘)if(m[num]==1){del(root,num);m[num]=0;}100             if(op==‘K‘){101                 if(num>t[root].siz)puts("invalid");102                 else{103                     int ans=query_num(root,num);104                     if(ans>=oo){105                         puts("invalid");106                         continue;107                     }108                     printf("%d\n",ans);109                 }110             }111             if(op==‘C‘)printf("%d\n",query_siz(root,num));112         }113     }114 }115 int main(){116     //freopen("input.in","r",stdin);117     using namespace solution;118     slove();119     return 0;120 }