#include <iostream>
using namespace std;

struct Node
{
    int key;
    int idx;
    Node* left;
    Node* right;
    Node* parent;
};

void preorderTraversal(Node* x)
{
    if (x != NULL)
    {
        std::cout << x->key << " ";
        preorderTraversal(x->left);
        preorderTraversal(x->right);
    }
    return;
}

void inorderTraversal(Node* x)
{
    if (x != NULL)
    {
        inorderTraversal(x->left);
        std::cout << x->key << " ";
        inorderTraversal(x->right);
    }
    return;
}

void postorderTraversal(Node* x)
{
    if (x != NULL)
    {
        postorderTraversal(x->left);
        postorderTraversal(x->right);
        std::cout << x->key << " ";
    }
    return;
}

void print_tree(Node* tree, int n)
{
    std::cout << std::endl;
    for (int i = 0; i < n; ++i)
    {
        std::cout << "i= " << tree[i].key << ": ";
        if (tree[i].left != NULL)
            std::cout << tree[i].left->key << " ";
        if (tree[i].right != NULL)
            std::cout << tree[i].right->key << " ;";
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

void find_parent(Node* max_vertex, Node* tree, Node* new_vertex)
{
    cout << "0" << endl;
    //cout << "запущен поиск родителя от " << max_vertex->key << " " << new_vertex->key << endl;
    cout << "запущен поиск родителя от " << max_vertex->key;

    print_tree(tree, 7);

    cout << "-1.5" << endl;
    if (tree[0].key <= new_vertex->key && tree[0].right == NULL)
    {
        cout << "-2" << endl;
        new_vertex->parent = &tree[0];
        tree[0].right = new_vertex;
    }

    else
    {
        cout << "-2.5" << endl;
        if (max_vertex->key <= new_vertex->key && max_vertex->right == NULL)
        {
            cout << "-3" << endl;
            new_vertex->parent = max_vertex;
            max_vertex->right = new_vertex;
        }

        else
        {
            cout << "-3.5" << endl;
            if (max_vertex->right != NULL)
            {
                cout << "-4" << endl;
                find_parent(max_vertex->right, tree, new_vertex);
            }

            else
            {
                cout << "-5" << endl;
                find_parent(max_vertex->left, tree, new_vertex);
            }

        }
    }

    cout << "end" << endl;
}

int main()
{
    int n;
    std::cin >> n;

    Node tree[n];
    for (int i = 0; i < n; ++i)
    {
        tree[i].right = NULL;
        tree[i].left = NULL;
        tree[i].parent = NULL;
        tree[i].idx = i;
        std::cin >> tree[i].key;
    }

    Node max_vertex = tree[0];

    cout << "1" << endl;
    for (int k = 0; k < n - 1; ++k)
    {

        if (max_vertex.key < tree[k].key)
            max_vertex = tree[k];

        cout << "сейчас k= " << k << endl;
        if (tree[k + 1].key < tree[k].key)
        {
            tree[k].left = &tree[k + 1];
            tree[k + 1].parent = &tree[k];
        }

        else
        {
            cout << "3" << endl;
            find_parent(&max_vertex, tree, &tree[k + 1]);
        }

        cout << "4" << endl;
    }

    print_tree(tree, n);

    postorderTraversal(&tree[0]);
    std::cout << std::endl;
    inorderTraversal(&tree[0]);

    return 0;
}