C++ :

#include<cstdio>
#include<algorithm>
#include<set>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=100000+10;
struct dong{
    int x,y;
    friend bool operator <(dong a,dong b){
        return a.y<b.y||a.y==b.y&&a.x<b.x;
    }
} zlt;
multiset<dong> s;
multiset<dong>::iterator it;
int tree[maxn][2],size[maxn],father[maxn],pp[maxn],sta[maxn],key[maxn];
bool bz[maxn];
int left[maxn],right[maxn];
int i,j,k,l,t,n,m,x,tot,top,ans,root;
bool czy,gjx;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int pd(int x){
    return tree[father[x]][1]==x;
}
void update(int x){
    size[x]=size[tree[x][0]]+size[tree[x][1]]+1;
}
void rotate(int x){
    int y=father[x],z=pd(x);
    father[x]=father[y];
    if (father[y]) tree[father[y]][pd(y)]=x;
    tree[y][z]=tree[x][1-z];
    if (tree[x][1-z]) father[tree[x][1-z]]=y;
    tree[x][1-z]=y;
    father[y]=x;
    if (pp[y]) pp[x]=pp[y],pp[y]=0;
    update(y);
    update(x);
}
void mark(int x){
    if (!x) return;
    bz[x]^=1;
    swap(tree[x][0],tree[x][1]);
}
void down(int x){
    if (bz[x]){
        mark(tree[x][0]);
        mark(tree[x][1]);
        bz[x]=0;
    }
}
void remove(int x,int y){
    top=0;
    while (x!=y){
        sta[++top]=x;
        x=father[x];
    }
    while (top) down(sta[top--]);
}
void splay(int x,int y){
    remove(x,y);
    while (father[x]!=y){
        if (father[father[x]]!=y)
            if (pd(x)==pd(father[x])) rotate(father[x]);else rotate(x);
        rotate(x);
    }
}
void access(int x){
    int y,z;
    splay(x,0);
    z=tree[x][1];
    if (z){
        pp[z]=x;
        father[z]=0;
    }
    tree[x][1]=0;
    update(x);
    while (1){
        y=pp[x];
        if (!y) break;
        splay(y,0);
        z=tree[y][1];
        if (z){
            pp[z]=y;
            father[z]=0;
        }
        tree[y][1]=x;
        father[x]=y;
        pp[x]=0;
        update(y);
        splay(x,0);
    }
}
void makeroot(int x){
    access(x);
    splay(x,0);
    mark(x);
}
void link(int x,int y){
    makeroot(y);
    splay(y,0);
    pp[y]=x;
}
void cut(int x,int y){
    makeroot(x);
    access(x);
    splay(y,0);
    pp[y]=0;
}
int getdep(int x){
    makeroot(root);
    access(x);
    splay(x,0);
    return size[tree[x][0]]+1;
}
int getfa(int x){
    makeroot(root);
    access(x);
    splay(x,0);
    int t=tree[x][0];
    if (!t) return 0;
    while (tree[t][1]){
        down(t);
        t=tree[t][1];
    }
    splay(t,0);
    return t;
}
void splaymin(){
    k=right[j];
    l=getfa(j);
    if (!l) return;
    cut(j,l);
    if (k) cut(j,k);
    if (k) link(l,k);
    left[l]=k;
    link(j,root);
    right[j]=root;
    root=j;
}
void splaymax(){
    k=left[j];
    l=getfa(j);
    if (!l) return;
    cut(j,l);
    if (k) cut(j,k);
    if (k) link(l,k);
    right[l]=k;
    link(j,root);
    left[j]=root;
    root=j;
}
void write(int x){
    if (!x){
        putchar('0');
        putchar('\n');
        return;
    }
    top=0;
    while (x){
        sta[++top]=x%10;
        x/=10;
    }
    while (top) putchar('0'+sta[top--]);
    putchar('\n');
}
int main(){
    m=read();
    while (m--){
        t=read();
        if (t==1){
            x=read();
            zlt.x=++tot;
            zlt.y=x;
            size[tot]=1;
            key[tot]=x;
            s.insert(zlt);
            it=s.find(zlt);
            if (it==s.begin()) czy=1;else czy=0;
            if ((++it)==s.end()) gjx=1;else gjx=0;
            it--;
            if (czy&&gjx) root=tot;
            else if (czy){
                k=(*(++it)).x;
                left[k]=tot;
                link(tot,k);
            }
            else if (gjx){
                k=(*(--it)).x;
                right[k]=tot;
                link(tot,k);
            }
            else{
                j=(*(--it)).x;it++;k=(*(++it)).x;
                if (getdep(j)<getdep(k)){
                    left[k]=tot;
                    link(tot,k);
                }
                else{
                    right[j]=tot;
                    link(tot,j);
                }
            }
            ans=getdep(tot);
        }
        else if (t==2||t==4){
            it=s.begin();
            j=(*it).x;
            ans=getdep(j);
            splaymin();
            if (t==4){
                root=right[j];
                if (root) cut(j,right[j]);
                zlt.x=j;zlt.y=key[j];
                s.erase(s.find(zlt));
            }
        }
        else{
            it=s.end();
            it--;
            j=(*it).x;
            ans=getdep(j);
            splaymax();
            if (t==5){
                root=left[j];
                if (root) cut(j,left[j]);
                zlt.x=j;zlt.y=key[j];
                s.erase(s.find(zlt));
            }
        }
        write(ans);
    }
}