#include <iostream>
using namespace std;
class bst{
    public:
    int data;
    bst *left,*right;
    
bst(int val){
    data = val;
    left = right = NULL;
}    
};

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

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

void leftViewUtil(bst *root,
                int level, int *max_level)
{
    if (root == NULL) return;
 
    if (*max_level < level)
    {
        cout << root->data << " ";
        *max_level = level;
    }
      leftViewUtil(root->left, level + 1, max_level);
    leftViewUtil(root->right, level + 1, max_level);
     
}

void leftView(bst *root)
{
    int max_level = 0;
    leftViewUtil(root, 1, &max_level);
}

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