#include <fstream>
#include <ctime>
#include <cstdlib>
#define maxn 500001

using namespace std;

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

int v[maxn],n;

//Partition2

void quicksort (int p, int q)
{
    if (q<=p) return;

    int x=v[rand()%(q-p+1)+p];

    int i, j = p-1;
    bool ok = 0;

    for (int i = p; i <= q; ++i)
    {
        if (v[i] < x)
        {
            ++j;
            swap (v[j],v[i]);
        }
        else if (v[i] == x)
        {
            if (ok)
            {
                ++j;
                swap (v[i],v[j]);
            }
            ok ^= 1;
        }
    }

    quicksort (p,j);
    quicksort (j+1,q);
}

int main()
{
    fin>>n;
    for (int i=1; i<=n; ++i) fin>>v[i];

    srand (time(NULL));
    quicksort (1,n);

    for (int i=1; i<=n; ++i) fout<<v[i]<<" ";
}