#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110 , M = 1010;
int l[M] , r[M] , w[M];
int n;

void dfs(int x , int root)
{
    if(x < root && l[root] == -1) l[root] = x , l[x] = -1 , r[x] = -1;
    else if(x > root && r[root] == -1) r[root] = x , l[x] = -1 , r[x] = -1;

    if(x > root) dfs(x , r[root]);
    else if(x < root)dfs(x , l[root]);
}

void f1(int x) // 前序遍历
{
    if(x == -1) return; 
    cout << x << ' ';
    f1(l[x]);
    f1(r[x]);
}


void f2(int x) // 中序遍历
{
    if(x == -1) return;
    f2(l[x]);
    cout << x << ' ';
    f2(r[x]);
}


void f3(int x) // 后序遍历
{
    if(x == -1) return;
    f3(l[x]);
    f3(r[x]);
    cout << x << ' ';
}

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> w[i];
    }

    l[w[0]] = -1 , r[w[0]] = -1;

    for(int i = 1 ; i < n ; i ++)
    {
        dfs(w[i] , w[0]);
    }

    f1(w[0]);
    puts("");
    f2(w[0]);
    puts("");
    f3(w[0]);
    puts("");
    return 0;
}