#include <fstream>
#include <ctime>
#include <stdlib.h>

using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");
int n, v[500001], i,p;

int rez(int st, int dr)
{
    int dst=0, ddr=-1;
    while(st!=dr)
    {
        if(v[st]>v[dr])
        {
            swap(v[st], v[dr]);
            swap(dst, ddr);
            ddr=-ddr;dst=-dst;
        }
        st+=dst;
        dr+=ddr;
    }
    return st;
}

void quicksort(int st, int dr)
{
    int p;
    if(st<dr)
    {
        p=rez(st, dr);
        quicksort(st, p-1);
        quicksort(p+1, dr);
    }
}

int main()
{
    srand(time(0));
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    for(i=n;i>1;i--)
    {
        p=1+1LL*(rand()*rand())%(i-1);
        swap(v[i], v[p]);
    }
    quicksort(1, n);
    for(i=1;i<=n;i++)
        fout<<v[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}