#include "iostream"
#include "cstdio"
using namespace std;

struct Node{
	int val;
	Node *left, *right;
	Node(int v = 0){
		val = v;
		left = NULL;
		right = NULL;
	}
};

inline void preOrder(Node *head){ //一定要加上inline才能过，否则会time limit
	if (head != NULL){
		printf(" %d", head->val);
		preOrder(head->left);
		preOrder(head->right);
	}
}
inline  void inOrder(Node *head){
	if (head != NULL){		
		inOrder(head->left);
		printf(" %d", head->val);
		inOrder(head->right);
	}
}

inline  void postOrder(Node *head){
	if (head != NULL){
		postOrder(head->left);
		postOrder(head->right);
		printf(" %d", head->val);
	}
}

inline  void buildTree(Node *&head, const int value){ //这里使用指针引用
	if (head == NULL){
		head = new Node(value);
	}
	else {
		if (head->val < value){
			buildTree(head->right ,value);
		}
		else
			buildTree(head->left, value);
	}
}

int main(){
	int n;
	bool ok = false;
	while (scanf("%d", &n) != EOF){
		if (ok)
			printf("\n");
		ok = true;
		Node *root = NULL;
		for (int i = 0; i < n; i++){
			int tmp;
			scanf("%d", &tmp);
			buildTree(root, tmp);
		}

		printf("Inorder:");
		inOrder(root);
		printf("\n");
		printf("Preorder:");
		preOrder(root);
		printf("\n");
		printf("Postorder:");
		postOrder(root);
		printf("\n");
	}
	return 0;
}

1310. Right-Heavy Tree