#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) {
            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; 
    }
    
    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; 
}