#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

ifstream fin("algsort.in");
ofstream fout("algsort.out");

const int mult=500005;
int nr_elem, v[mult];

void citire()
{
    fin>>nr_elem;
    nr_elem--;
    for(int i=0; i<=nr_elem; i++)
    {
        fin>>v[i];
    }
}

void afisare()
{
    for(int i=0; i<=nr_elem; i++)
        fout<<v[i]<<' ';
    fout<<'\n';
}


void quicksort(int st, int dr)
{
    afisare();
    if(st>=dr)
    {
        return;
    }
    if(st+1==dr)
    {
        if(v[st]>v[dr])
            swap(v[st], v[dr]);
        return;
    }
    int piv=dr;
    swap(v[piv], v[dr]);
    int free_pos=st;
    for(int i=st; i<dr; i++)
    {
        if(v[i]<=v[dr])
        {
            swap(v[free_pos], v[i]);
            free_pos++;
        }
    }
    swap(v[dr], v[free_pos]);
    quicksort(st, free_pos-1);
    quicksort(free_pos+1, dr);
}


int main()
{
    srand(time(0));
    citire();
    quicksort(0, nr_elem);
    afisare();
    return 0;
}