#include <bits/stdc++.h>

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

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 quicks(int li,int lf)
{
    if(li >= lf)
        return;
    int piv = li + rand() % (lf - li + 1);
    int m = part(li,lf,piv);
    quicks(li,m-1);
    quicks(m+1,lf);
}

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

void Print()
{
    srand(unsigned(time(0)));
    quicks(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;
}