#include <fstream>
#include <algorithm>
#include <math.h>
#include <assert.h>

inline int partition(int* arr, int low, int high, int* lp); 
  
inline void swap(int* a, int* b) { 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 
  
inline void DualPivotQuickSort(int* arr, int low, int high) { 
    if (low < high) { 
        int lp, rp;  
        rp = partition(arr, low, high, &lp); 
        DualPivotQuickSort(arr, low, lp - 1); 
        DualPivotQuickSort(arr, lp + 1, rp - 1); 
        DualPivotQuickSort(arr, rp + 1, high); 
    } 
} 
  
inline int partition(int* arr, int low, int high, int* lp) { 
    if (arr[low] > arr[high]) 
        swap(&arr[low], &arr[high]); 
    int j = low + 1; 
    int g = high - 1, k = low + 1, p = arr[low], q = arr[high]; 
    while (k <= g) { 
  
        if (arr[k] < p) { 
            swap(&arr[k], &arr[j]); 
            j++; 
        } else if (arr[k] >= q) { 
            while (arr[g] > q && k < g) 
                g--; 
            swap(&arr[k], &arr[g]); 
            g--; 
            if (arr[k] < p) { 
                swap(&arr[k], &arr[j]); 
                j++; 
            } 
        } 
        k++; 
    } 
    j--; 
    g++; 
  
    swap(&arr[low], &arr[j]); 
    swap(&arr[high], &arr[g]); 
  
    *lp = j;
    return g; 
} 

int main() {
	std::ifstream cin("algsort.in");
	std::ofstream cout("algsort.out");
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;

	assert(1 <= n && n <= 500000);
	int v[n];

	for (int i = 0 ; i < n ; ++i) {
		cin >> v[i];
	}

	DualPivotQuickSort(v, 0, n - 1);

	for (int i = 0 ; i < n ; ++i) {
		cout << v[i] << " ";
	}

	cout << '\n';
	return 0;
}