#include <algorithm>
#include <iostream>
#include <vector>

struct Node {
    Node(int x) {
        key = x;
        left = nullptr;
        right = nullptr;
    }
    int key;
    Node* left;
    Node* right;
};
Node* BSTConstruction(const std::vector<int>& preorder, int& index, int low, int high) {
    if (index >= preorder.size()) {
        return nullptr;
    }
    int current_key = preorder[index];
    if (current_key <= low || current_key > high) {
        return nullptr;
    }
    Node* current_node = new Node(current_key);
    index++;
    current_node->left = BSTConstruction(preorder, index, low, current_key);
    current_node->right = BSTConstruction(preorder, index, current_key, high);
    return current_node;
}
void InOrder(const Node* node) {
    if (node == nullptr) {
        return;
    }
    InOrder(node->left);
    std::cout << node->key << ' ';
    InOrder(node->right);
}
void PostOrder(const Node* node) {
    if (node == nullptr) {
        return;
    }
    PostOrder(node->left);
    PostOrder(node->right);
    std::cout << node->key << ' ';
}
void PrintPostIn(const Node* root) {
    PostOrder(root);
    std::cout << '\n';
    InOrder(root);
}
void PostOrderDelete(Node* root) {
    if (root == nullptr) {
        return;
    }
    PostOrderDelete(root->left);
    PostOrderDelete(root->right);
    root->left = nullptr;
    root->right = nullptr;
    delete root;
}
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int num;
    int index = 0;
    std::cin >> num;
    std::vector<int> keys(num);
    for (int i = 0; i != num; i++) {
        std::cin >> keys[i];
    }
    Node* root = BSTConstruction(keys, index, -1, 1000000000);
    PrintPostIn(root);
    PostOrderDelete(root);
    return 0;
}