/**********************************************************************************/
/* Problem: d526 "Binary Search Tree (BST)" from BST */
/* Language: CPP (1158 Bytes) */
/* Result: AC(72ms, 2.2MB) judge by this@ZeroJudge */
/* Author: saitor362320 at 2012-09-02 00:32:36 */
/**********************************************************************************/
//#include<stdafx.h>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node{
node* left;
node* right;
node* par;
int val;
};
node* TreeInsert(node* root, int v)
{
//initial node
node* block = (node*) malloc(sizeof(node));
block->left = NULL;
block->right = NULL;
block->par = NULL;
block->val = v;
//find new node's parent
node* temp = root;
node* parent = NULL;
while(temp!=NULL){
parent = temp;
if(block->val<temp->val)
temp=temp->left;
else
temp=temp->right;
}
block->par = parent;
if(parent==NULL) //tree is empty
root = block;
else if(block->val < parent->val)
parent->left = block;
else
parent->right = block;
return root;
}
void PreOrder(node* x)
{
if(x!=NULL){
cout << x->val << ' ';
PreOrder(x->left);
PreOrder(x->right);
}
}
int main()
{
int num;
while(cin>>num){
node* BST_Root = NULL;
for(int i=0;i<num;++i){
int input;
cin >> input;
BST_Root = TreeInsert(BST_Root,input);//cout<<BST_Root<<endl;
}
// output answer
PreOrder(BST_Root);
cout << endl;
}
return 0;
}