//土尔逊Torson 编写于2023/06/10
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>

using namespace std;

struct TreeNode10601 {
	int data;
	TreeNode10601* leftChild;
	TreeNode10601* rightChild;
	TreeNode10601(int x):data(x),leftChild(NULL),rightChild(NULL){}
};

TreeNode10601* Insert(TreeNode10601* root, int x) {
	if (root == NULL) {                    //创建新结点
		root = new TreeNode10601(x);
	}
	else if (x < root->data) {             //插入左子树
		root->leftChild = Insert(root->leftChild, x);
	}
	else if (root->data < x) {             //插入右子树
		root->rightChild = Insert(root->rightChild, x);
	}
	return root;
}

void PreOrder10601(TreeNode10601* root) {       //前序遍历
	if (root == NULL) {
		return;
	}
	printf("%d ", root->data);
	PreOrder10601(root->leftChild);
	PreOrder10601(root->rightChild);
	return;
}

void InOrder10601(TreeNode10601* root) {      //中序遍历
	if (root == NULL) {
		return;
	}
	InOrder10601(root->leftChild);
	printf("%d ", root->data);
	InOrder10601(root->rightChild);
	return;
}

void PostOrder10601(TreeNode10601* root) {    //后序遍历
	if (root == NULL) {
		return;
	}
	PostOrder10601(root->leftChild);
	PostOrder10601(root->rightChild);
	printf("%d ", root->data);
	return;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		TreeNode10601* root = NULL;        //建立空树
		for (int i = 0; i < n; ++i) { //逐个插入
			int x;
			scanf("%d", &x);
			root = Insert(root, x);
		}
		PreOrder10601(root);
		printf("\n");
		InOrder10601(root);
		printf("\n");
		PostOrder10601(root);
		printf("\n");
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")