#include
using namespace std;
struct node{
int data;
node* left;
node* right;
};
node* buildbst(node *root,int data){
if(root==NULL){
root =new node;
root->data=data;
root->left=NULL;
root->right=NULL;
return root;
}
if(data>=root->data){
root->left=buildbst(root->left,data);
}
if(data<=root->data){
root->right=buildbst(root->right,data);
}
return root;
}
void printPreorder(node* node)
{
if (node == NULL)
return;
/* first print data of node */
cout << node->data << " ";
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
node* balanced(int l,int r,int a[],node *root){
if(l<=r){
return root;
}
int mid=(l+r)/2;
root=buildbst(root,a[mid]);
balanced(l,mid,a,root);
balanced(mid+1,r,a,root);
}
int main() {
int m;
cin>>m;
for(int i=0;i<m;i++){
int n;
cin>>n;
int a[n];
for(int j=0;j<n;j++){
cin>>a[j];
}
node* root=NULL;
root=balanced(0,n-1,a,root);
printPreorder(root);
}
return 0;
}