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

#define N 500000

int v[N], n;

void schimb(int *a, int *b)
{
    int aux = *a;
    *a = *b;
    *b = aux;
}

void scrie(int v[], int st, int dr)
{
    int i;
    for (i = st; i <= dr; i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}

void partitie3(int v[], int st, int dr, int *p1, int *p2)
{
    *p1 = st;
    *p2 = dr - 1;
    int i = st;
    while (i <= *p2)
    {
        if (v[i] <= v[dr])
        {
            if (v[i] < v[dr])
            {
                schimb(&v[i], &v[*p1]);
                (*p1)++;
            }
            i++;
        }
        else
        {
            schimb(&v[i], &v[*p2]);
            (*p2)--;
        }
    }
    (*p2)++;
    schimb(&v[dr], &v[*p2]);
}

void qs(int v[], int st, int dr)
{
    if (st >= dr)
    {
        return;
    }
    int  p1, p2;
    partitie3(v, st, dr, &p1, &p2);
    qs(v, st, p1 - 1);
    qs(v, p2 + 1, dr);
}

int main()
{
    freopen("algsort.in", "r", stdin);
    freopen("algsort.out", "w", stdout);
    int i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &v[i]);
    }
    ///amestec
    srand(time(0));
    int p;
    for (i = n - 1; i >= 0; i--)
    {
        p = rand() % (i + 1);
        schimb(&v[i], &v[p]);
    }
    qs(v, 0, n - 1);
    scrie(v, 0, n - 1);
    return 0;
}