#include <bits/stdc++.h>


using namespace std;


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

const int NMAX = 3000002;

int k; int n;

int v[NMAX];

void quick(int st, int dr) {

    if(st >= dr)
        return ;

    int p = st + rand() % (dr - st + 1);

    swap(v[dr], v[p]);

    int index = st - 1;

    //intre st si index elemente mai mici decat pivotul v[dr] inclusiv
    //intre index + 1 si dr elemente mai mare sau egale ca pivotul

    for(int i = st; i < dr ; ++i) {
        if(v[i] < v[dr]) {
            index++;
            swap(v[i], v[index]);
            continue;
        }

        if(v[i] == v[dr] && rand() % (1<<10)  > (1<<9) ) {

            index++;
            swap(v[i], v[index]);
        }
    }



    swap(v[dr], v[index + 1]);



     quick(st, index);

     quick(index + 2, dr);

}


int main() {

    srand(time(NULL));

    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

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

    quick(1, n);


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