#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

using namespace std;
ifstream in("algsort.in");
ofstream out("algsort.out");

const int N=500010;
int n,v[N];
int rpartition(int p,int r);
int partition(int p,int r);

void read()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
}

void qs(int p,int r)
{
    int q;
    if(p<r)
    {
        q=rpartition(p,r);
        qs(p,q-1);
        qs(q+1,r);
    }
}
void sw(int i,int j)//swap
{
    int k;
    k=v[i];
    v[i]=v[j];
    v[j]=k;
}

int partition(int p,int r)
{
    int x=v[r];
    int i=p-1;
    for(int j=p;j<=r-1;j++)
    {
        if(v[j]<=x)
        {
            ++i;
            sw(i,j);
        }
    }
    sw(i+1,r);
    return i+1;
}

int rpartition(int p,int r)
{
    srand(time(NULL));
    int i=(rand()%(n-1))+1;
    sw(r,i);
    return partition(p,r);
}


void print()
{
    for(int i=1;i<=n;i++)
        out<<v[i]<<" ";
    out<<'\n';
}
int main()
{
    read();
    qs(1,n);
    print();

    return 0;
}