#include <fstream>
#include <cstdlib>
#include <ctime>
#define SIZE 500000
#define RANDOM(a, b) ((rand() % (b-a+1)) + a)
using namespace std;


ifstream ifs("algsort.in");
ofstream ofs("algsort.out");

int A[SIZE], N;

void swap(int n1, int n2)
{
    int aux = A[n1];
    A[n1] = A[n2];
    A[n2] = aux;
}

int random_partition(int left, int right)
{
    int r = RANDOM(left, right);
    swap(left, r);
    
    int x = A[left];
    
    int i = left - 1;
    int j = right + 1;
    
    while (true)
    {
        do 
        {
            ++i;
        } while (A[i] < x);
        
        do
        {
            --j;
        } while (A[j] > x);
        
        
        if (i < j)
        {
            swap(i, j);
        }
        else
        {
            return j;
        }
    }
}

void random_quicksort(int left, int right)
{
    if (left < right)
    {
        int pivot = random_partition(left, right);
        random_quicksort(left, pivot);
        random_quicksort(pivot+1, right);
    }
}

int main()
{
    ifs >> N;
    for (int i = 0; i < N; ++i)
    {
        ifs >> A[i];
    }
    
    // Init random seed
    srand(time(NULL));
    
    random_quicksort(0, N-1);
    
    for (int i = 0; i < N; ++i)
    {
        ofs << A[i] << " ";
    }

    return 0;
}