1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <queue>  6 #define KT ch[ch[root][1]][0]  7 #define LC ch[x][0]  8 #define RC ch[x][1]  9 #define N 210001 10 #define lson l,mid,rt<<1|1 11 #define rson mid+1,r,rt<<1 12 #define Root 1,n,1 13 using namespace std; 14  15 typedef long long LL; 16 struct xds{ 17     int a[N<<2]; 18     int n; 19     void init(int nn){ 20         n=nn; 21         build(Root); 22     } 23     void pushup(int rt){ 24         if(a[rt<<1|1]==-1){ 25             a[rt]=a[rt<<1]; 26         } 27         else{ 28             a[rt]=a[rt<<1|1]; 29         } 30     } 31     void build(int l,int r,int rt){ 32         if(l==r){ 33             a[rt]=l; 34             return; 35         } 36         int mid=(l+r)>>1; 37         build(lson); 38         build(rson); 39         pushup(rt); 40     } 41  42     void updata(int x,int f,int l,int r,int rt){ 43         if(l==r){ 44             if(f) a[rt]=-1; 45             else a[rt]=l; 46             return; 47         } 48         int mid=(l+r)>>1; 49         if(x<=mid)updata(x,f,lson); 50         else updata(x,f,rson); 51         pushup(rt); 52     } 53     int query(int L,int R,int l,int r,int rt){ 54         if(L<=l&&r<=R){ 55             return a[rt]; 56         } 57         int mid=(l+r)>>1; 58         int ans=query(L,R,lson); 59         if(ans!=-1)return ans; 60         return query(L,R,rson); 61     } 62     void push(int val){ 63         updata(val,0,Root); 64     } 65     int top(){ 66         return query(1,n,Root); 67     } 68     void pop(){ 69         updata(top(),1,Root); 70     } 71 }Q; 72 struct SplayTree{ 73     int root; 74     int fa[N]; 75     int ch[N][2]; 76     int sz[N]; 77     int top1; 78     int top2; 79     int ss[N]; 80     int que[N]; 81  82     void pushdown(int x){ 83  84     } 85     void pushup(int x){ 86         sz[x]=1+sz[LC]+sz[RC]; 87  88         sum[x]=val[x]+sum[LC]+sum[RC]; 89         neg[x]=(val[x]<0) + neg[LC]+neg[RC]; 90     } 91     void rotate(int x,bool f){ 92         int y=fa[x]; 93         int z=fa[y]; 94         pushdown(y); 95         pushdown(x); 96         ch[y][!f]=ch[x][f]; 97         fa[ch[x][f]]=y; 98         fa[x]=z; 99         if (z) {100             ch[z][ch[z][1]==y] = x;101         }102         ch[x][f] = y;103         fa[y]=x;104         pushup(y);105     }106     void splay(int x, int g) {107         int y = fa[x];108         pushdown(x);109         while(y!=g){110             int z= fa[y];111             bool f = (ch[y][0]==x);112             if(z != g && f == (ch[z][0]==y)){113                 rotate(y,f);114             }115             rotate(x,f);116             y=fa[x];117         }118         pushup(x);119         if(g==0) root = x;120     }121     void rotateTo(int k,int g) {122         int x=root;123         pushdown(x);124         while(sz[LC] != k){125             if(k<sz[LC]){126                 x=LC;127             }else{128                 k -= sz[LC] + 1;129                 x = RC;130             }131             pushdown(x);132         }133         splay(x,g);134     }135     void build(int l,int r,int f){136         if(l>r){137             return ;138         }139         int x = (l + r) >> 1;140         LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0;141         RC = (r >= x + 1)? (x + 1 + r)>> 1 :0;142         fa[x] = f;143         build(l,x - 1,x);144         build(x + 1,r,x);145         pushup(x);146     }147     void erase(int x){148         if(x==0)149             return;150         int father= fa[x];151         int head = 0, tail=0;152         for(que[tail++] =x ; head < tail; head++){153             ss[top2++] = que[head];154             if(ch[que[head]][0]){155                 que[tail++]=ch[que[head]][0];156             }157             if(ch[que[head]][1]){158                 que[tail++] = ch[que[head]][1];159             }160         }161         ch[father][ch[father][1]==x]=0;162         pushup(father);163     }164     void treaval(int x){165         if (x) {166             pushdown(x);167             treaval(LC);168             printf("@%d",val[x]);169 170             treaval(RC);171         }172     }173     int idx(int v){174         if(v==0)return 0;175         if(v>0)return v;176         else177             return -v+N;178     }179     void newNode(int &x,int c){180         if(top2){181             x = ss[--top2];182         } else {183             x = ++top1;184         }185         LC = RC = fa[x] =0;186         sz[x] = 1;187         val[x] = c;188         sum[x] = c;189         neg[x] = (c<0);190         pos[idx(c)]=x;191     }192     void makeTree(int &x, int l, int r, int f){193         if(l > r){194             return;195         }196         int m=(l+r)>>1;197         newNode(x, num[m]);198         makeTree(LC,l,m-1,x);199         makeTree(RC,m+1,r,x);200         fa[x]=f;201         pushup(x);202     }203     void debug(){204         treaval(root);205         cout<<endl;206     }207     int dfs_max(int x){208        pushdown(x);209        if(RC)return dfs_max(RC);210        return x;211     }212     int dfs_min(int x){213         pushdown(x);214         if(LC)return dfs_min(LC);215         return x;216     }217     void dele(int x){218         splay(x,0);219 //        int pre=dfs_max(LC);220 //        int nex=dfs_min(RC);221         int pre=sz[LC]-1;222         int nex=pre+2;223         rotateTo(pre,0);224         rotateTo(nex,root);225         erase(x);226         pushup(ch[root][1]);227         pushup(root);228     }229     int find(int x,int k){230         if(neg[LC]==k&&val[x]<0){splay(x,0);return sz[LC];}231         else if(neg[LC]>k){232             return find(LC,k);233         }else{234             return find(RC,k-neg[LC]-(val[x]<0));235         }236     }237     void insert(int p,int a){238 239         rotateTo(p-1,0);240         rotateTo(p,root);241         num[1]=a;242         makeTree(KT,1,1,ch[root][1]);243         pushup(ch[root][1]);244         pushup(root);245     }246 247     void insert(int p){248         int a=Q.top();Q.pop();249         insert(p+1,a);250         rotateTo(p+1,0);251         int posnum=sz[ch[root][0]]-neg[ch[root][0]]-1;252         if(posnum==neg[root]){253             insert(sz[root]-1,-a);254         }else{255             int k=find(root,posnum);256             insert(k,-a);257         }258     }259     void remove(int v){260         int x=pos[idx(v)];261         dele(x);262         x=pos[idx(-v)];263         dele(x);264 265         Q.push(v);266     }267     LL query(int v){268         int x1 = pos[idx(v)];269         int x2 = pos[idx(-v)];270         splay(x1,0);271         splay(x2,root);272         return sum[KT];273     }274     void init(){275         top1=top2=root=0;276         newNode(root,0);277         newNode(ch[root][1],0);278         fa[ch[root][1]]=root;279         pushup(ch[root][1]);280         pushup(root);281     }282     void solve(int n){283         int a;284         char op[10];285         Q.init(n+1);286         //for(int i=1;i<=n+1;i++)Q.push(i);287         for(int i=1;i<=n;i++){288             //debug();289             scanf("%s%d",op,&a);290             if(op[0]==‘i‘){291                 insert(a);292             }else if(op[0]==‘r‘){293                 remove(a);294             }else{295                 printf("%I64d\n",query(a));296             }297         }298     }299     int num[N];300     int val[N];301     LL sum[N];302     int pos[N*2];303     int neg[N];304     xds Q;305     //priority_queue <int,vector<int>,greater<int> > Q;306 }spt;307 308 int main(){309     int n;310     int cas=1;311     while(scanf("%d",&n)!=EOF){312         printf("Case #%d:\n",cas++);313         spt.init();314         spt.solve(n);315     }316 }