//treap数据结构的代码实现保存
#include<bits/stdc++.h>
inline void read(int &a)
{
	a=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
inline void write(int a)
{
	if(a<0){putchar('-');a=-a;}
	if(a>9)write(a/10);
	putchar(a%10+'0');
}
struct node
{
	int order,key,num;
	node* son[2];
	inline int comp(int x)
	{
		if(key==x)return -1;
		if(x<key)return 0;
		return 1;
	}
	inline bool operator>(const node* &b)
	{
		if(order>b->order)return true;
		return false;
	}
};
inline node newnode(int x)
{
	node p; 
	p.son[0]=p.son[1]=0;
	p.order=rand();
	p.num=0;
	p.key=x;
	return p;
}
inline void update(node* &p)
{
	p->num=1;
	if(p->son[0]!=NULL)p->num+=p->son[0]->num;
	if(p->son[1]!=NULL)p->num+=p->son[1]->num;
}
inline void rotate(node* &p,int d)
{
	node* t=p->son[d];
	p->son[d]=t->son[d^1];
	t->son[d^1]=p;
	update(p);update(t);
}
inline void insert(node* &p,int x)
{
	int d=p->comp(x);
	if(d==-1)return ;
	insert(p->son[d],x);
	if(p->son[d]>p)rotate(p,d);
	else update(p);
}
inline void remove(node* &p,int x)
{
	int d=p->comp(x);
	if(d==-1)
    {
        node *u=p;
        if(p->son[0]!=NULL&&p->son[1]!=NULL)
        {
            int dd;
			if(p->son[0]>p->son[1])dd=0;
			else dd=1;
            rotate(p,dd);
            remove(p->son[dd],x);
        }
        else
        {
            if(p->son[0]==NULL)p=p->son[1];
            else p=p->son[0];
            delete u;
        }
    }
	else remove(p->son[d],x);
}
int main()
{
	srand(time(NULL));
	return 0;
}