Description

H 国是一个热爱写代码的国家，那里的人们很小去学校学习写各种各样的数据结构。

伸展树（splay）是一种数据结构，因为代码好写，功能多，效率高，掌握这种数据结构成为了 H 国的必修技能。

有一天，邪恶的“卡”带着他的邪恶的“常数”来企图毁灭 H 国。

“卡”给 H 国的人洗脑说，splay 如果写成单旋的，将会更快。

“卡”称“单旋 splay”为“spaly”。

虽说他说的很没道理，但还是有 H 国的人相信了，小 H 就是其中之一，spaly 马上成为他的信仰。

而 H 国的国王，自然不允许这样的风气蔓延，国王构造了一组数据，数据由 m 个操作构成，他知道这样的数据肯定打垮 spaly。

但是国王还有很多很多其他的事情要做，所以统计每个操作所需要的实际代价的任务就交给你啦。

数据中的操作分为五种：

1. 插入操作：向当前非空 spaly 中插入一个关键码为 key 的新孤立节点。

插入方法为，先让 key 和根比较，如果 key 比根小，则往左子树走，否则往右子树走。

如此反复，直到某个时刻，key 比当前子树根 x 小，而 x 的左子树为空，那就让 key 成为 x 的左孩子；

或者 key 比当前子树根 x 大，而 x 的右子树为空，那就让 key 成为 x 的右孩子。

该操作的代价为：插入后，key 的深度。

特别地，若树为空，则直接让新节点成为一个单个节点的树。（各节点关键码互不相等。对于“深度”的解释见末尾对 spaly 的描述）。

2. 单旋最小值：将 spaly 中关键码最小的元素 xmin 单旋到根。操作代价为：单旋前 xmin 的深度。

（对于单旋操作的解释见末尾对 spaly 的描述）。

3. 单旋最大值：将 spaly 中关键码最大的元素 xmax 单旋到根。操作代价为：单旋前 xmax 的深度。

4. 单旋删除最小值：先执行 2 号操作,然后把根删除。由于 2 号操作之后,根没有左子树,所以直接切断根和右子

树的联系即可（具体见样例解释）。 操作代价同 2 号操 作。

5. 单旋删除最大值：先执行 3 号操作,然后把根删除。 操作代价同 3 号操作。

 

对于不是 H 国的人，你可能需要了解一些 spaly 的知识，才能完成国王的任务：

a. spaly 是一棵二叉树，满足对于任意一个节点 x，它如果有左孩子 lx，那么 lx 的关键码小于 x 的关键码。

如果有右孩子 rx，那么 rx 的关键码大于 x 的关键码。

b. 一个节点在 spaly 的深度定义为：从根节点到该节点的路径上一共有多少个节点（包括自己）。

c. 单旋操作是对于一棵树上的节点 x 来说的。

一开始,设 f 为 x 在树上的父亲。如果 x 为 f 的左孩子，那么执行 zig(x) 操作（如上图中，左边的树经过 zig(x) 变为了右边的树）；

否则执行 zag(x) 操作（在上图中，将右边的树经过 zag(f) 就变成了左边的树）。

每当执 行一次 zig(x) 或者 zag(x)，x 的深度减小 1，如此反复，直到 x 为根。

总之，单旋 x 就是通过反复执行 zig 和 zag 将 x 变为根。

Input

第一行单独一个正整数 m。

接下来 m 行，每行描述一个操作：

首先是一个操作编号 c∈[1,5]，即问题描述中给出的五种操作中的编号，若 c = 1，则再输入一个非负整数 key，表示新插入节点的关键码。

1≤m≤10^5,1≤key≤10^9

所有出现的关键码互不相同。

任何一个非插入操作，一定保证树非空。

在未执行任何操作之前，树为空

Output

输出共 m 行，每行一个整数，第 i 行对应第 i 个输入的操作的代价。

Sample Input

5

1 2

1 1

1 3

4

5

Sample Output

1

2

2

2

2

---

题解Here!

这题目，毒瘤到掉牙了。。。

我调了一下午，中途还因为太毒了去水了一道网络流。。。

$AHOI/HNOIDAY1T1$这么毒，出题人怕是要上天了。。。

不过这题真的蛮神的。。。

用一个数据结构维护另外一个数据结构，出题人异想天开啊。。。

首先，你需要会单旋，就是这个样子：

inline void turn(int rt,int k){	int x=a[rt].f,y=a[x].f;	pushdown(x);pushdown(rt);	a[x].son[k^1]=a[rt].son[k];	if(a[rt].son[k])a[a[rt].son[k]].f=x;	a[rt].f=y;	if(y)a[y].son[a[y].son[1]==x]=rt;	a[x].f=rt;	a[rt].son[k]=x;	pushup(x);pushup(rt);}void spaly(int rt,int ancestry){	while(a[rt].f!=ancestry)turn(rt,a[a[rt].f].son[0]==rt);    if(ancestry==0)root=rt;}

这样你就有20分暴力了。。。

然后，慢慢分析单旋的性质。

1. 插入操作：

我们会发现这样一个事实：

一个节点的插入所经过的$Spaly$路径，必然经过这个节点的$key$值在$Spaly$上的前驱与后继！

并且新插入的节点一定在前驱与后继中深度更深的节点的儿子节点上！

那就好办了，我们只要找到$key$的前驱与后继就可以了。

怎么找？

拿出了$Spaly$的原型——双旋的$Splay$！

$Splay$的复杂度是$O(\log_2n)$的，当然可以胜任。

于是只要$Splay$上的节点与$Spaly$的节点的编号一一对应就可以了。

为了方便，我们让它们相同。

找到$key$的前驱与后继了，就挂在前驱的右儿子，或者是后继的左儿子上，看那个深度更深就是了。

这个操作完美解决。

2. 单旋最小值：

我们知道，$Spaly$与$Splay$的最小值一定没有左儿子！

我们可以手动模拟一下$Spaly$上的最小值单旋到根的过程。（尽量把$Spaly$的深度画成3或者4，方便寻找规律）

我们又发现了一个事实：

当最小值单旋到根之后，最小值的深度为1（这不废话嘛）。

此时最小值仅有右子树。

但右子树即为除了最小值的$Spaly$！

并且形态只改变了一点：原来最小值的右子树 / 接到了 / 原来最小值的父亲的左子树 / 上！（“/”表停顿）

而且深度还没有变！

听得比较绕。。。

但是这个性质让我们可以用$Splay$维护某节点在$Spaly$上的深度！

把最小值的深度改为$1$不用多说。

之后呢？

先将最小值的右子树打上$-1$的标记（以后会抵消），再在$Splay$上旋转到根，然后对其右子树打上$+1$标记（抵消了前面的$-1$标记）。

那，$Spaly$的形态怎么维护呢？

把最小值与其父亲的父子关系断开，最小值与其右儿子的父子关系断开，将最小值的右儿子与最小值的父亲连上父子关系，最小值的右儿子挂在最小值的父亲的左儿子上。

再将最小值与原来$Spaly$的根节点连上父子关系，最小值为父亲。

然后每次旋转的时候不要忘了$pushdown$一下。。。

然后就没了。。。

3. 单旋最大值：

这个跟操作2差不多吧，省略。。

4. 单旋删除最小值：

题目都说了先执行操作2。。。

然后按照题目所说断开最小值（现在的根节点）与原来的根节点的父子关系，之后把根节点换成原来的根节点，并打上$+1$的标记。

然后就没了啊。。。

5. 单旋删除最大值：

同操作4，这里就省略了。

呼~终于解决了！

总复杂度应该是$Splay$的复杂度，即均摊$O(n\log_2n)$。

这题真的是毒瘤。。。

真心膜拜考场上写出来的那些大佬。。。

反正本蒟蒻顶多20分。。。

因为就算想出来了，也没有时间敲+调试了。。。

调试代码毁天灭地，鄙人把它们删掉了。

附上删掉毁天灭地的调试代码之后仍然毁天灭地的代码：

#include
      
       #include
       
        #include
        
         #define MAXN 100010using namespace std;int n,m=0,size=1,root=0,head;struct Splay{	int f,s,son[2];	int v,c,key;}a[MAXN];struct Spaly{	int f,son[2];}b[MAXN];inline int read(){	int date=0,w=1;char c=0;	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}inline void clean(int rt){	a[rt].son[0]=a[rt].son[1]=a[rt].f=a[rt].s=a[rt].v=a[rt].c=0;	b[rt].f=b[rt].son[0]=b[rt].son[1]=0;}inline void pushup(int rt){	if(!rt)return;	a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+1;}inline void pushdown(int rt){	if(!rt||!a[rt].c)return;	if(a[rt].son[0]){		a[a[rt].son[0]].c+=a[rt].c;		a[a[rt].son[0]].v+=a[rt].c;	}	if(a[rt].son[1]){		a[a[rt].son[1]].c+=a[rt].c;		a[a[rt].son[1]].v+=a[rt].c;	}	a[rt].c=0;}inline void turn(int rt,int k){	int x=a[rt].f,y=a[x].f;	pushdown(x);pushdown(rt);	a[x].son[k^1]=a[rt].son[k];	if(a[rt].son[k])a[a[rt].son[k]].f=x;	a[rt].f=y;	if(y)a[y].son[a[y].son[1]==x]=rt;	a[x].f=rt;	a[rt].son[k]=x;	pushup(x);pushup(rt);}void splay(int rt,int ancestry){	while(a[rt].f!=ancestry){		int x=a[rt].f,y=a[x].f;		pushdown(y);pushdown(x);pushdown(rt);		if(y==ancestry)turn(rt,a[x].son[0]==rt);		else{			int k=a[y].son[0]==x;			if(a[x].son[k]==rt){turn(rt,k^1);turn(rt,k);}			else{turn(x,k);turn(rt,k);}		}	}	if(ancestry==0)root=rt;}inline int newnode(int fa,int key){	int rt=size++;	if(fa)a[fa].son[a[fa].key
         
          a[y].s+1){			k-=a[y].s+1;			rt=a[rt].son[1];		}		else if(k<=a[y].s)rt=y;		else return rt;	}}int front_next(int rt,int x,int k){	find(rt,x);	rt=root;	if((a[rt].key>x&&k)||(a[rt].key
          
           a[next].v)fa=front;	else fa=next;	a[rt].v=a[fa].v+1;	b[rt].f=fa;	if(fa)b[fa].son[a[fa].key