#include <iostream>
#include <fstream>
#include <ctime>

#define NMAX 500000
#define max(a,b) ((a)<(b))?(a):(b)

const char IN[] = "algsort.in", OUT[] = "algsort.out";

using namespace std;

int N;
int v[NMAX];
int inOrder;
bool comboBreaker;

inline void swap(int poz1, int poz2) {
	if (&v[poz1] != &v[poz2]) {
		v[poz1] = v[poz1] ^ v[poz2];
		v[poz2] = v[poz2] ^ v[poz1];
		v[poz1] = v[poz1] ^ v[poz2];
	}
}

inline void readData() {
	freopen(IN, "r", stdin);
	scanf("%d", &N);
	scanf("%d", &v[0]);
	int vmax = v[0];
	for (int i = 1; i < N; ++i) {
		scanf(" %d", &v[i]);
		if (!comboBreaker) {
			if (v[i] < vmax) comboBreaker |= 1;
			else ++inOrder, vmax = max(vmax, v[i]);
		}
	}
	fclose(stdin);
}

inline int partition(int low, int high, int pivot) {
	int pivotVal = v[pivot];
	swap(pivot, high);
	int index = low;
	for (int i = low; i < high; ++i) {
		if (v[i] < pivotVal) swap(i, index), ++index;
	}
	swap(high, index);
	return index;
}

void qsort(int low, int high) {
	if (low == high - 1) (v[low] > v[high]) ? (swap(high, low)):void();
	if (low < high) {
		int m = low + rand() % ((low == high) ? 1 : (high - low));
		int index = partition(low, high, m);
		qsort(low, index - 1);
		qsort(index + 1, high);
	}
}

int main() {
	readData();
	srand(time(NULL));
	if (inOrder != N) qsort(inOrder, N - 1);
	freopen(OUT, "w", stdout);
	for (int i = 0; i < N; ++i)
		printf("%d ", v[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}