#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

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

int A[500001];

int part_Hoare ( int s, int d )
{

    int r_m, r1, r2, r3;


    int i, j;
    i = s-1;
    j= d+1;

    int nr = d-s+1;

    //int randpoz = rand()% nr + s;
    r1 = rand() % nr + s;
    //cout<<r1<<'\n';
    r2 = rand() % nr + s;
    //cout<<r2<<'\n';
    r3 = rand() % nr + s;
    //cout<<r3<<'\n';
    int minr, maxr;
    minr = min ( min(r1, r2), min(r2, r3) );
    maxr = max ( max(r1, r2), max(r2, r3) );
    r_m = r1+r2+r3 - minr-maxr;
    //cout<<r_m<<'\n'<<'\n';
    int pivot = A[r_m];



    //int pivot = A[randpoz];
    while (true){
        do
        {
            ++i;
        }while( A[i] < pivot);
        do
        {
            --j;
        }while( A[j] > pivot);
        if( i>=j )
            return j;
        swap(A[i], A[j]);
    }
}

void qsort (int i, int j)
{
    if(i<j){
        int k = part_Hoare( i, j );
        qsort(i, k);
        qsort(k+1, j);
    }
}


int main()
{
    int N, i;
    fin>>N;
    cout<<"N:"<<N<<endl;
    for( i=1; i<=N; i++ )
        fin>>A[i];
    fin.close();
    qsort(1, N);
    for( i=1; i<=N; i++ )
        fout<<A[i]<<" ";
    fout.close();
}