#include <bits/stdc++.h>
using namespace std;

typedef struct node {
    int data;
    struct node* lchild, *rchild;
}* BitTree;

void InsertBitTree(BitTree& T, int x) {
    if (T == NULL) {
        T = new node;
        T ->data = x;
        T ->lchild = NULL;
        T ->rchild = NULL;
        return;
    }
    if (x == T->data) return;
    else if (x < T ->data) InsertBitTree(T ->lchild, x);
    else InsertBitTree(T->rchild, x);
}

void InOrderPrint(BitTree T) {
    if (T != NULL) {
        InOrderPrint(T->lchild);
        cout << T->data << " ";
        InOrderPrint(T->rchild);
    }
}

void PreOrderPrint(BitTree T) {
    if (T != NULL) {
        cout << T->data << " ";
        PreOrderPrint(T->lchild);
        PreOrderPrint(T->rchild);
    }
}

void LastOrderPrint(BitTree T) {
    if (T != NULL) {
        LastOrderPrint(T->lchild);
        LastOrderPrint(T->rchild);
        cout << T->data << " ";
    }
}

int main() {
    int n, x;
    while (cin >> n) {
        BitTree T = NULL;
        for (int i = 1; i <= n; i++) {
            cin >> x;
            InsertBitTree(T, x);
        }
        PreOrderPrint(T);
        cout << endl;
        InOrderPrint(T);
        cout << endl;
        LastOrderPrint(T);
    }
}