#include <iostream>
using namespace std;

class bst{
    public:
    int data;
    bst *left, *right;
    
bst(int value){
    data = value;
    left = right = NULL;
}

};

bst* insert(bst* root,int value){
    if(root == NULL){
        return new bst(value);
    }
    if(value > root->data){
        root->right = insert(root->right,value);
    }
    else{
        root->left = insert(root->left,value);
    }
    return root;
}


void inorder(bst* root){
    if(root == NULL){
        return;
    }
    else{
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void preorder(bst* root){
    if(root == NULL){
        return;
    }
    else{
        cout<<root->data<<" ";
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(bst* root){
    if(root == NULL){
        return;
    }
    else{
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<" ";
    }
}

int main() {
    bst *root = NULL;
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        root=insert(root,x);
    }
    preorder(root);
    cout<<"\n";
    inorder(root);
    cout<<"\n";
    postorder(root);
    return 0;
}