#include <iostream> 
using namespace std;

int findNextR(int l, int size, int *arr) {
	for (int i = l; i < size; ++i) {
		if (arr[i] < 0)
			return i;
	}
	return size - 1;
}

int partition(int l, int r, int *arr) {
	long pivot = arr[(l + r) / 2];
	while (l <= r) {
		while (arr[r] > pivot)
			r--;
		while (arr[l] < pivot)
			l++;
		if (l <= r) {
			long tmp = arr[r];
			arr[r] = arr[l];
			arr[l] = tmp;
			l++;
			r--;
		}
	}
	return l;
}
void quickSort(int size, int *arr) {
	int l = 0;
	int r = size - 1;
	int q, i = 0;
	int tmpr = r;
	while (true) {
		i--;
		while (l < tmpr) {
			q = partition(l, tmpr, arr);
			arr[tmpr] = -arr[tmpr];
			tmpr = q - 1;
			++i;
		}
		if (i < 0)
			break;
		l++;
		tmpr = findNextR(l, size, arr);
		arr[tmpr] = -arr[tmpr];
	}
}

int main() {
	int size;
	cin >> size;
	int *arr = new int[size];

	quickSort(size, arr);

	return 0;
}