struct node{int ch[2],fa,val,right;}t[MN];
int tot=0,root;
int build(int v){t[++tot].val=v;t[tot].right=0;return tot;}

void setc(int f,int c,bool r){t[f].ch[r]=c;t[c].fa=f;t[c].right=r;}
void rotate(int o,int sty)//sty=0 left
{
	int x=t[o].ch[sty],f=t[o].fa;
	if(o==root){root=x;t[x].fa=0;t[x].right=0;}
	else setc(f,x,t[o].right);
	setc(o,t[x].ch[sty^1],sty);
	setc(x,o,1^sty);
}

void splay(int o)
{
	int f,g;
	while(o!=root)
	{
		f=t[o].fa;g=t[f].fa;
		if(f==root){rotate(f,t[o].right);return;}
		if(g&&t[f].right==t[o].right)
			rotate(g,t[f].right);
		rotate(f,t[o].right);
	}
}