#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");
srand(time(NULL));
void qsort(int st,int dr)
{
    if(st==dr)return;
    pivot=(st+dr)/2;//pivot=rand()%(dr-st+1)+st;
    swap(a[st],a[pivot]);
    pivot=st;
    for(int i=st+1;i<=dr;i++)
    {
        if(a[pivot]>a[i]&&pivot>i)
            swap(a[pivot],a[i]),pivot=i;
        if(a[pivot]<a[i]&&pivot<i&&i-pivot!=1)
        {
            swap(a[pivot],a[pivot+1]),pivot++;
            if(i-pivot!=1)
            swap(a[pivot-1],a[i]);
        }
    }
    qsort(pivot,dr);
    qsort(st,pivot);
}
int main()
{
    ///QUICKSORT
    fin>>n;
    for(int i=1;i<=n;i++)fin>>a[i];
    return 0;
}