#include <iostream>
#include <fstream>
#include <cstdlib>
#include<ctime>
using namespace std;
int v[1000], n;
void citeste()
{
    ifstream f("sortare.txt");
    f>>n;
    for (int i=1;i<=n;i++)
        f>>v[i];
    f.close();

}
int pivot(int li, int ls)
{
    int a, b, c;
    a=rand() % ls +li;
    b=rand() % ls +li;
    c=rand() % ls +li;
    if ((v[a]<=v[b]&& v[a]>=v[c]) || (v[a]<=v[c] && v[a]>=v[b])) return a;
    if ((v[b]<=v[a]&& v[b]>=v[c]) || (v[b]<=v[c] && v[b]>=v[a])) return b;
    if ((v[c]<=v[b]&& v[a]<=v[c]) || (v[a]>=v[c] && v[c]>=v[b])) return c;
}
void sorteaza(int st, int dr)
{
    srand(time(NULL));

    int aux;
    if (dr-st>=2)
    {int p;
    if (dr-st>10) p=pivot(st, dr);
    else p=rand() % (dr-1) +st;
    srand(time(NULL));
    int i=st, j=p+1;
    while (i<=p && j<=dr)
        {if (v[i]<v[p]) i++;
         if (v[j]>v[p]) j++;
         if (v[i]>=v[p] && v[j]<=v[p] && i<=dr && j<=dr) {aux=v[i]; v[i]=v[j];v[j]=aux;}
    sorteaza (st, p);
    sorteaza (p, dr);
    }
    }
    else if (dr-st==1) if (v[st]>v[dr]) {aux=v[st]; v[st]=v[dr]; v[dr]=aux;}
}
void afiseaza()
{
    for (int i=1;i<=n;i++)
        cout<<v[i]<<" ";

}
int main()
{
    citeste();
    sorteaza(1,n);
    afiseaza();
}