// Sortare prin comparare folosind quicksort cu alegerea pivotului ultimul element

#include <fstream>

#include <random>

#include <time.h>

#include <algorithm>



using namespace std;



ifstream fin("algsort.in");

ofstream fout("algsort.out");



static const int NMAX = 5e5+5;



int n;

int v[NMAX];



void PrintOutput()

{

    for(int i =1; i<= n;++i)

        fout << v[i] << " ";

    fout << endl;

}



int part(int arr[], int low, int high)

{

    int pivot1 = low + rand() % (high - low + 1);

    int pivot2 = low + rand() % (high - low + 1);

    int pivot3 = low + rand() % (high - low + 1);



    int pivot = (pivot1 + pivot2 + pivot3) - min(pivot1,min(pivot2,pivot3))

    -max(pivot1,max(pivot2,pivot3));



    swap(arr[pivot], arr[high]);



    int i = low -1;

    int j = high +1;



    while(true)

    {

        do{

            i++;

        }while(arr[i] < arr[pivot]);



        do

        {

            j--;

        }while(arr[j] > arr[pivot]);



        if(i >= j)

            return j;

        swap(arr[i],arr[j]);

    }

}



void Quicksort(int arr[], int low, int high)

{

    if(low < high)

    {

        int pi = part(arr,low,high);

        Quicksort(arr,low, pi);

        Quicksort(arr, pi+1, high);

    }



}



void ReadInput()

{

    fin >> n;

    for(int i =1; i<= n;++i)

        fin >> v[i];

}





int main()

{

    // Inititalise random seed

    srand(time(NULL));



    ReadInput();

    Quicksort(v,1,n);

    PrintOutput();

    return 0;

}