#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct TreeNode {
  ElemType val;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PTreeNode;

PTreeNode insertIntoBST(PTreeNode root, ElemType val) {
  if (!root) {
    root = (PTreeNode) malloc(sizeof(TreeNode));
    root->val = val;
    root->left = root->right = NULL;
    return root;
  }

  if (val < root->val)
    root->left = insertIntoBST(root->left, val);
  else if (val > root->val)
    root->right = insertIntoBST(root->right, val);

  return root;
}

void output(PTreeNode node) {
  fprintf(stdout, "%d ", node->val);
}

void preorder(PTreeNode root, void (*visit) (PTreeNode)) {
  if (!root) return;
  visit(root);
  preorder(root->left, visit);
  preorder(root->right, visit);
}

void inorder(PTreeNode root, void (*visit) (PTreeNode)) {
  if (!root) return;
  inorder(root->left, visit);
  visit(root);
  inorder(root->right,visit);
}

void postorder(PTreeNode root, void (*visit) (PTreeNode)) {
  if (!root) return;
  postorder(root->left, visit);
  postorder(root->right, visit);
  visit(root);
}

int main(const int argc, const char** argv) {
  int n, x;
  scanf("%d", &n);

  PTreeNode root = NULL;
  while (n--) {
    scanf("%d", &x);
    root = insertIntoBST(root, x);
  }

  preorder(root, output);
  fputc(10, stdout);

  inorder(root, output);
  fputc(10, stdout);

  postorder(root, output);
  fputc(10, stdout);
  return 0;
}