#include <bits/stdc++.h>

using namespace std;
int p = 0;
int A[3666013],N;
int Stack[3666013][2],vf;

int part(int li,int lf,int index)
{
    swap(A[lf],A[index]);
    for(int i = li; i < lf; ++i)
    {
        if(A[i] < A[lf])
            swap(A[li++],A[i]);
        if(A[i] == A[lf] && (p ^= 1))
            swap(A[li++],A[i]);
    }
    swap(A[lf],A[li]);
    return li;
}

void quicksITER(int li,int lf)
{
    ++vf;
    Stack[vf][0] = li;
    Stack[vf][1] = lf;
    while(vf)
    {
        li = Stack[vf][0];
        lf = Stack[vf][1];
        vf--;
        if(li >= lf)
            continue;
        int piv = li + rand() % (lf - li + 1);
        int m = part(li,lf,piv);
        ++vf;
        Stack[vf][0] = li;
        Stack[vf][1] = m-1;
        ++vf;
        Stack[vf][0] = m+1;
        Stack[vf][1] = lf;
    }
}

void quicksRec(int li,int lf)
{
    if(li >= lf)
        return;
    int piv = li + rand() % (lf - li + 1);
    int m = part(li,lf,piv);

    if(m - li < lf - m)
    {
        quicksRec(li, m - 1);
        quicksITER(m + 1, lf);
        return;
    }
    quicksRec(m + 1, lf);
    quicksITER(li,m - 1);
}

void Read()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
        scanf("%d",&A[i]);
}

void Print()
{
    srand(unsigned(time(0)));
    quicksRec(1,N);
    for(int i = 1; i <= N; ++i)
        printf("%d ",A[i]);
}

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);

    Read();
    Print();

    return 0;
}