#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
inline void swap(int &x,int &y){x^=y^=x^=y;}
inline int max(const int &a,const int &b){return a>b?a:b;}
const int N=1e5+13;
struct Lct{
	struct Stack{
		int s[N],t;
		inline void clear(){t=0;}
		Stack(){clear();}
		inline void push(int x){s[++t]=x;}
		inline void pop(){--t;}
		inline int top(){return s[t];}
		inline bool empty(){return !t;}
	};
	int fa[N],siz[N],ch[N][2];bool tag[N];
	inline void refresh(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
	inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
	inline bool chk(int x){return ch[fa[x]][1]==x;}
	inline void rotate(int x){
		int f=fa[x],gf=fa[f],k=chk(x),w=ch[x][k^1];
		fa[x]=gf;if(!isroot(f)) ch[gf][chk(f)]=x;
		if(w) fa[w]=f;ch[f][k]=w;
		fa[f]=x;ch[x][k^1]=f;
		refresh(f),refresh(x);
	}
	inline void pushdown(int x){
		if(!tag[x]) return;
		tag[ch[x][0]]^=1,tag[ch[x][1]]^=1,tag[x]=0;
		swap(ch[x][0],ch[x][1]);
	}
	inline void splay(int x){
		Stack st;int p=x;
		while(!isroot(p)) st.push(p),p=fa[p];
		st.push(p);
		while(!st.empty()) pushdown(st.top()),st.pop();
		while(!isroot(x)){
			int f=fa[x];
			if(!isroot(f)){
				if(chk(f)==chk(x)) rotate(f);
				else rotate(x);
			}
			rotate(x);
		}
	}
	inline void access(int x){
		for(int p=0;x;p=x,x=fa[x]) splay(x),ch[x][1]=p,refresh(x);
	}
	inline void makeroot(int x){access(x);splay(x);tag[x]^=1;}
	inline int findroot(int x){
		access(x);splay(x);
		while(ch[x][0]) x=ch[x][0];
		return x;
	}
	inline void split(int x,int y){makeroot(x);access(y);splay(y);}
	inline void link(int x,int y){
		if(!x||!y) return;
		makeroot(x);
		fa[x]=y;
	}
	inline void cut(int x,int y){
		if(!x||!y) return;
		split(x,y);
		ch[y][0]=fa[x]=0,refresh(x),refresh(y);
	}
	inline int finddep(int x,int y){//对每一个点找深度 
		split(x,y);
		return siz[y];
	}
}T;
int m,tot,rt,op[N],a[N],b[N],Cnt,f[N],c[N][2];
set<int> t;
set<int>::iterator it;
int main(){
//	freopen("splay1.in","r",stdin);
//	freopen("splay.out","w",stdout);
	scanf("%d",&m);
	for(int i=1;i<=m;++i) T.siz[i]=1;
	for(int i=1;i<=m;++i){
		scanf("%d",&op[i]);
		if(op[i]==1) scanf("%d",&a[i]),b[++tot]=a[i];
	}
	sort(b+1,b+tot+1);tot=unique(b+1,b+tot+1)-b-1;
	for(int i=1;i<=m;++i){
		switch(op[i]){
			case 1:{
				int x=lower_bound(b+1,b+tot+1,a[i])-b;
				int pre=0,suf=0;
				if(!Cnt){//注意特判，这个题因为涉及到边界的地方很多，所以需要很多特判 
					t.insert(x);rt=x;
					puts("1");++Cnt;
					continue;
				}
				t.insert(x);it=t.find(x);++Cnt;
				if(it!=t.begin()) pre=*(--it),++it;//找前驱和后继的set操作不太一样，要注意 
				++it;
				if(it!=t.end()) suf=*it;
				int r1=pre?T.finddep(rt,pre):0,r2=suf?T.finddep(rt,suf):0;
				if(r1<r2){
					printf("%d\n",r2+1);
					f[x]=suf,c[suf][0]=x,T.link(x,suf);
				}
				else{
					printf("%d\n",r1+1);
					f[x]=pre,c[pre][1]=x,T.link(x,pre);
				}
				break;
			}
			case 2:{
				it=t.begin();int x=*it;
				if(rt==x){puts("1");continue;}
				printf("%d\n",T.finddep(rt,x));
				int u=c[x][1],v=f[x];//开了两个数组来记录原树 
				T.cut(x,v),T.cut(x,u),T.link(x,rt),T.link(v,u);
				f[x]=0,c[x][1]=rt,f[rt]=x;rt=x;
				c[v][0]=u;f[u]=v;
				break;
			}
			case 3:{
				it=t.end();int x=*(--it);
				if(rt==x){puts("1");continue;}
				printf("%d\n",T.finddep(rt,x));
				int u=c[x][0],v=f[x];
				T.cut(x,v),T.cut(x,u),T.link(x,rt),T.link(v,u);
				f[x]=0,c[x][0]=rt,f[rt]=x;rt=x;
				c[v][1]=u;f[u]=v;
				break;
			}
			case 4:{
				it=t.begin();int x=*it;t.erase(x);
				printf("%d\n",T.finddep(rt,x));
				--Cnt;
				if(!Cnt) continue;
				int u=c[x][1],v=f[x];
				T.cut(x,v),T.cut(x,u);T.link(u,v);
				c[x][0]=c[x][1]=f[x]=0;if(rt==x) rt=u;//别忘了更新根节点 
				c[v][0]=u;f[u]=v;
				break;
			}
			case 5:{
				it=t.end();int x=*(--it);t.erase(x);
				printf("%d\n",T.finddep(rt,x));
				--Cnt;
				if(!Cnt) continue;
				int u=c[x][0],v=f[x];
				T.cut(x,v),T.cut(x,u);T.link(u,v);
				c[x][0]=c[x][1]=f[x]=0;if(rt==x) rt=u;
				c[v][1]=u;f[u]=v;
				break;
			}
		}
	}
	return 0;
}