#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <ctime>

#define MAX_N 500000

int n, v[MAX_N];

void read( FILE *fin ) {
    assert( fscanf( fin, "%d", &n ) == 1 );
    for ( int i = 0; i < n; ++i )
        assert( fscanf( fin, "%d", &v[i] ) == 1 );
}

void write( FILE *fout ) {
    for ( int i = 0; i < n; ++i )
        fprintf( fout, "%d ", v[i] );
}

int get_pivot( int a, int b ) {
    int len = b - a + 1;
    int p1 = v[a + rand() % len], p2 = v[a + rand() % len], p3 = v[a + rand() % len];

    int min = p1 < p2 ? p1 : p2, max = p1 > p2 ? p1 : p2;
    min = p3 < min ? p3 : min;
    max = p3 > max ? p3 : max;

    int mid = p1 + p2 + p3 - max - min;

    return mid;
}

void swap( int &a, int &b ) {
    int aux = a;
    a = b;
    b = aux;
}

void qsort( int left, int right ) {
    if ( left >= right )
        return;

    int piv = get_pivot( left, right ), begin = left, end = right;
    
    while ( begin <= end ) {
        while ( v[begin] < piv )
            ++begin;
        while ( v[end] > piv )
            --end;

        if ( begin <= end ) {
            swap( v[begin], v[end] );
            ++begin;
            --end;
        }
    }

    qsort( left, end );
    qsort( begin, right );
}

int main() {
    srand( time( NULL ) );

    FILE *fin, *fout;

    fin = fopen( "algsort.in", "r" );
    read( fin );
    fclose( fin );

    qsort( 0, n - 1 );

    fout = fopen( "algsort.out", "w" );
    write( fout );
    fclose( fout );
}