#include <iostream>
#include <fstream>
#include <list>
#include <cstdlib>
#include <time.h>
using namespace std;

typedef list <int> lista;
typedef list <lista :: iterator> pnt;
pnt point;
lista L, E;

int main () {
    ifstream cin("algsort.in");
    ofstream cout("algsort.out");
    srand(time(NULL));
    int n, x;
    cin >> n >> x;
    L.push_back(x);
    E.push_back(x);
    point.push_back(L.begin());

    for( int i = 1; i < n; ++i) {
        cin>>x;

        lista :: iterator it = E.begin();
        pnt :: iterator pos = point.begin();
        while (it != E.end() && *it < x) {
            ++it;
            ++pos;
        }
        --it;
        --pos;

        lista :: iterator match = *pos;
        while (match != L.end() && *match < x)
            ++match;
        L.insert(match, x);
        --match;
        cout<<*match<<" "<<x<<endl;
        int lst = rand() % 500;
        if (lst == 0) {
            E.insert(it, x);
            point.insert(pos, match);
        }
        /*
        for( it = L.begin(); it != L.end(); ++it)
            cout<<*it<<" ";
        cout<<endl<<endl;
        */
    }

    for (lista :: iterator it = L.begin() ; it != L.end() ; ++it)
        cout << *it << " ";

    return 0;
}