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

using namespace std;

#define MAXN 500001
int A[MAXN];



void randomizePartition(int p, int r);
// QuickSort - average case O(N logN), worst case O(N^2)-> sorted array
// WC: partition of 1.

void partition(int p, int r) {
    int x = A[r];
    int left = p;
    for (int i = p; i < r; i++) {
        if (A[i] <= x) {
            if (left != i) {
                swap(A[left], A[i]);
            }
            left++;
        }
    }
    swap(A[left], A[r]);
    randomizePartition(p, left - 1);
    randomizePartition(left + 1, r);

}

void randomizePartition(int p, int r) {
    if (p >= r) {
        return;
    }
    s
            int q = rand() % (r - p) + p;
    swap(A[q], A[r]);
    partition(p, r);
}

int main() {
    freopen("algsort.in", "r", stdin);
    freopen("algsort.out", "w", stdout);
    int N;
    scanf("%d", &N);
    int x;
    for (int i = 0; i < N; i++) {
        scanf("%d", &x);
        A[i] = x;
    }
    srand(time(NULL));
    randomizePartition(0, N - 1);
    for (int i = 0; i < N - 1; i++) {
        printf("%d ", A[i]);
    }
    printf("%d\n", A[N - 1]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}