Description：

定义 $spaly$ 为单旋的 $splay$ ，维护一个 $spaly$ ，支持插入，把最小值旋到根，把最大值旋到根，删除根，输出操作位置的深度。

$1\leqslant n\leqslant 10^5$

Solution：

首先直接按照题意单旋模拟肯定随便就卡成 $O(n^2)$ 了，考虑有什么更好的做法，手玩一下会发现实际上单旋最小值影响的点非常小，那么就可以用一个类似 $splay$ 的东西来模拟它，插入的时候有一个性质，就是一定是插入在前驱的右儿子或者后继的左儿子，并且一定只有一个位置是空的，所以插在对应位置就好了，单旋最小值的话就是胡乱接一下，注意根节点的更新，统计深度可以用线段树，因为每次都是整个子树深度增加或减少，找到对应的区间操作就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXN 100010

int n;

set<int> st;

struct opt

{

	int type,x;

}o[MAXN];

int b[MAXN],tot = 0;

namespace Seg

{

	struct node

	{

		int lc,rc;

		int tag;

		node(){tag = 0;}

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void pushdown(int rt)

	{

		t[t[rt].lc].tag += t[rt].tag;

		t[t[rt].rc].tag += t[rt].tag;

		t[rt].tag = 0;

		return;

	}

	void add(int rt,int L,int R,int k,int l,int r)

	{

		if(L <= l && r <= R)

		{

			t[rt].tag += k;

			return;

		}

		pushdown(rt);

		if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

		if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

		return;

	}

	void set(int rt,int p,int k,int l,int r)

	{

		if(l == r)

		{

			t[rt].tag = k;

			return;

		}

		pushdown(rt);

		if(p <= mid)set(t[rt].lc,p,k,l,mid);

		else set(t[rt].rc,p,k,mid + 1,r);

		return;

	}

	int query(int rt,int p,int l,int r)

	{

		if(l == r)return t[rt].tag;

		pushdown(rt);

		if(p <= mid)return query(t[rt].lc,p,l,mid);

		else return query(t[rt].rc,p,mid + 1,r);

	}

}

namespace Spaly

{

	struct node

	{

		int c[2],fa;

		node(){c[0] = c[1] = fa = 0;}

	}t[MAXN];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root = 0;

	void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

	int insert(int k)

	{

		st.insert(k);

		if(root == 0)

		{

			root = k;

			Seg::set(Seg::root,k,1,1,tot);

			return 1;

		}

		set<int>::iterator it = st.find(k);

		int p;

		if(it == st.begin())p = *(++it);

		else

		{

			set<int>::iterator pr = it;--pr;

			if(t[*pr].c[1] != 0)p = *(++it);

			else p = *pr;

		}

		if(k > p)connect(k,p,1);

		else connect(k,p,0);

		int depk = Seg::query(Seg::root,p,1,tot) + 1;

		Seg::set(Seg::root,k,depk,1,tot);

		return depk;

	}

	int calcmin()

	{

		int p = *(st.begin());

		if(p == root)return 1;

		int res = Seg::query(Seg::root,p,1,tot);

		int f = t[p].fa;

		t[p].fa = 0;

		connect(t[p].c[1],f,0);

		Seg::add(Seg::root,f,tot,1,1,tot);

		connect(root,p,1);

		root = p;

		Seg::set(Seg::root,p,1,1,tot);

		return res;

	}

	int calcmax()

	{

		int p = *(st.rbegin());

		if(p == root)return 1;

		int res = Seg::query(Seg::root,p,1,tot);

		int f = t[p].fa;

		t[p].fa = 0;

		connect(t[p].c[0],f,1);

		Seg::add(Seg::root,1,f,1,1,tot);

		connect(root,p,0);

		root = p;

		Seg::set(Seg::root,p,1,1,tot);

		return res;

	}

	void removeroot()

	{

		Seg::add(Seg::root,1,tot,-1,1,tot);

		st.erase(root);

		Seg::set(Seg::root,root,0,1,tot);

		root = t[root].c[0] + t[root].c[1];

		t[root].fa = 0;

		return;

	}

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		o[i].type = rd();

		if(o[i].type == 1)

		{

			o[i].x = rd();

			b[++tot] = o[i].x;

		}

	}

	sort(b + 1,b + 1 + tot);

	for(int i = 1;i <= n;++i)

	{

		if(o[i].type == 1)o[i].x = lower_bound(b + 1,b + 1 + tot,o[i].x) - b;

	}

	Seg::build(Seg::root,1,tot);

	for(int i = 1;i <= n;++i)

	{

		if(o[i].type == 1)printf("%d\n",Spaly::insert(o[i].x));

		if(o[i].type == 2)printf("%d\n",Spaly::calcmin());

		if(o[i].type == 3)printf("%d\n",Spaly::calcmax());

		if(o[i].type == 4)printf("%d\n",Spaly::calcmin());

		if(o[i].type == 5)printf("%d\n",Spaly::calcmax());

		if(o[i].type == 4 || o[i].type == 5)Spaly::removeroot();

	}

	return 0;

}