#include<stdio.h>
#include<stdlib.h>
typedef int Treedata;
typedef struct Node
{
	Treedata data;
	struct Node *leftchild,*rightchild;
}treenode;
typedef treenode *tree;
treenode* creatTree(treenode *T,int x)
{
	if(T==NULL)
	{
		T=(treenode *)malloc(sizeof(treenode));
		    T->data=x;
			T->leftchild=NULL;
			T->rightchild=NULL;
	}
	else if(T->data>x)
	{
		T->leftchild=creatTree(T->leftchild,x);
	}
	else if(T->data<x)
	{
		T->rightchild=creatTree(T->rightchild,x);
	}
	else ;
	return T;
}
void preorder(treenode *T)
{
	if(T!=NULL)
	{	
		printf("%d ",T->data);
		preorder(T->leftchild);
		preorder(T->rightchild);
	}
}
void inorder(treenode *T)
{
	if(T!=NULL)
	{
		inorder(T->leftchild);
		printf("%d ",T->data);
		inorder(T->rightchild);
	}
}
void postorder(treenode *T)
{
	if(T!=NULL)
	{  
		postorder(T->leftchild);
		postorder(T->rightchild);		
		printf("%d ",T->data);
	}
}
void cleantree(treenode *T)
{
	if(T)
	{
		cleantree(T->leftchild);
		cleantree(T->rightchild);
		free(T);
	}
}
void main()
{
	int i,n,x;
	treenode *T;
	while(scanf("%d",&n)!=EOF)
	{   
		for(i=0,T=NULL;i<n;i++)
		{   
	        scanf("%d",&x);
          	T=creatTree(T,x);
		}
         preorder(T);
		 printf("\n");
         inorder(T);
         printf("\n");
         postorder(T);
         printf("\n");
         cleantree(T);
	}
}
/**************************************************************
	Problem: 2195
	User: admin
	Language: C
	Result: Accepted
	Time:9 ms
	Memory:1144 kb
****************************************************************/