/*

Quick Sort- varianta din CLR + pivot random

*/
using namespace std;
#include<iostream>
#include<fstream>
#include<cstdlib>
#define nmax 500010
ofstream fout("algsort.out");
int N,a[nmax];
int select(int l,int r)
{
    int i,j;

    int popiv;
    popiv=rand()%(r-l+1)+l;
    swap(a[l],a[popiv]);

    int pivot;
    pivot=a[l];
    i=l;
    j=r;
    while(i<j)
    {



        while(a[i]<=pivot && i<=r) i++;
        while(a[j]>pivot && j>=l)  j--;
        if(i<j)
        {
            swap(a[i],a[j]);
        }


    }
    int m=j;
    swap(a[l],a[m]);

 return m;
}

void qsort(int l,int r)
{
    if(l>r) return;
    int p=select(l,r);

    qsort(l,p-1);
    qsort(p+1,r);

}

void cit()
{
    ifstream fin("algsort.in");
    fin>>N;
    int i;
    for(i=1;i<=N;i++)
    {

        fin>>a[i];
    }

    fin.close();

}

int main()
{
    srand(time(0));
    cit();

    qsort(1,N);
    int i;
    for(i=1;i<=N;i++)
    {

        fout<<a[i]<<" ";
    }
    fout.close();
    return 0;
}