struct Treap{
	struct node{
		int l,r,val,key,siz,cnt;
	}t[maxn];
	int tot,root;

	int New(int x){
		t[++tot].val=x;
		t[tot].key=rand();
		t[tot].siz=t[tot].cnt=1;
		return tot;
	}

	void push_up(int x){t[x].siz=t[t[x].l].siz+t[t[x].r].siz+t[x].cnt;}

	void zig(int &x){
		int y=t[x].l;
		t[x].l=t[y].r;
		t[y].r=x;
		x=y;
		push_up(t[x].r);
		push_up(x);
	}

	void zag(int &x){
		int y=t[x].r;
		t[x].r=t[y].l;
		t[y].l=x;
		x=y;
		push_up(t[x].l);
		push_up(x);
	}

	void insert(int &x,int val){
		if(x==0)return x=New(val),void();
		if(t[x].val==val)return ++t[x].cnt,++t[x].siz,void();
		if(valt[x].val){
			insert(t[x].r,val);
			push_up(x);
			if(t[x].key1)return --t[x].cnt,--t[x].siz,void();
			if(!t[x].l&&!t[x].r)return x=0,void();
			if(!t[x].r||t[t[x].l].key>t[t[x].r].key)return zig(x),erase(t[x].r,val),push_up(x);
			if(!t[x].l||t[t[x].l].keyval)ans=min(ans,t[x].val),x=t[x].l;
			else x=t[x].r;
		}
		return ans;
	}
	
	int kth(int x,int th){
		if(th<=t[t[x].l].siz)return kth(t[x].l,th);
		if(th<=t[t[x].l].siz+t[x].cnt)return t[x].val;
		return kth(t[x].r,th-t[t[x].l].siz-t[x].cnt);
	}
}T;

struct FHQ_Treap{
	struct node{
		int l,r,size,val,key;
	}t[maxn];
	int tot,root;
	int New(int x){t[++tot].val=x;t[tot].key=rand();t[tot].size=1;return tot;}
	void push_up(int x){t[x].size=t[t[x].l].size+t[t[x].r].size+1;}
	void split(int x,int &rtx,int &rty,int val){
		if(x==0)return rtx=rty=0,void();
		if(val=id)return kth(t[x].l,id);
		return kth(t[x].r,id-t[t[x].l].size-1);
	}
	int rank(int x){
		int l=0,r=0,ans=0;
		split(root,l,r,x-1);
		ans=t[l].size+1;
		root=merge(l,r);
		return ans;
	}
	int pre(int x){
		int l=0,r=0,ans=0;
		split(root,l,r,x-1);
		ans=kth(l,t[l].size);
		root=merge(l,r);
		return ans;
	}
	int nxt(int x){
		int l=0,r=0,ans=0;
		split(root,l,r,x);
		ans=kth(r,1);
		root=merge(l,r);
		return ans;
	}
}T;