学步园

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
int n,t,root,size;
bool f;
struct data{
	int l,r,v,rnd;
}tr[50001];
void lturn(int &k){
	int t=tr[k].r;
	tr[k].r=tr[t].l;
	tr[t].l=k;
	k=t;
}
void rturn(int &k){
	int t=tr[k].l;
	tr[k].l=tr[t].r;
	tr[t].r=k;
	k=t;
}
void insert(int &k,int x){
	if(!k){
		k=++size;
		tr[k].v=x;
		tr[k].rnd=rand();
		return;
	}
	if(tr[k].v==x){
		f=1;return;
	}
	else if(x<tr[k].v){
		insert(tr[k].l,x);
		if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
	}
	else{
		insert(tr[k].r,x);
		if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		memset(tr,0,sizeof(tr));
		scanf("%d",&n);
		root=size=f=0;
		for(int i=1;i<=n;i++){
			int x;scanf("%d",&x);f=0;
			insert(root,x);
			if(!f){
				if(i==1)printf("%d",x);
				else printf(" %d",x);
			}
		}
		printf("\n");
	}
}