#include "iostream"
#include "stdlib.h"
#include "fstream"
using namespace std;
int v[500005],n;
void citeste(int v[],int &n)
{
    int i;
    ifstream f;
    f.open("algsort.in");
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f.close();
}
void qs(int s,int d)
{
    int i,j;
    int aux;
    int pivot;
    i=s;j=d;
    pivot = v[rand() % i+j];
    while(i<=j){

        while(v[i]<pivot){i++;}
        while(v[j]>pivot){j--;}
        if(i<=j){aux=v[i];v[i]=v[j];v[j]=aux;i++;j--;}
        if(s<j) qs(s,j);
        if(i<d) qs(i,d);

    }
}
void afis(int v[],int n)
{
    int i;
    ofstream g;
    g.open("algsort.out");
    for(i=1;i<=n;i++)
        g<<v[i]<<" ";
    g.close();
}
int main()
{
    citeste(v,n);
    qs(1,n);
    afis(v,n);
    return 0;
}