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

typedef struct ewd { int val; } EWD;
//prvek spojového seznamu
typedef struct prvekSeznamu  {
	//záznam EWD (jen pro ilustraci, že s daty EWD se nehýbe -- v celém programu se jinak nepoužívá)
	EWD zaznam;
	//stáří záznamu (čím starší, tím vyšší číslo)
	int stari;
	//ukazatel na další prvek spojového seznamu (nebo hodnota NULL, pokud je poslední)
	struct prvekSeznamu *dalsi;
} PrvekSeznamu;

//nerekurzivní metoda, která dostane ukazatel na první prvek nesetříděného seznamu a vrátí ukazatel
//na první prvek setříděného seznamu
PrvekSeznamu *EWDSort(PrvekSeznamu *zacatek) {
	if (zacatek == NULL) return NULL; //algoritmus dostal prázdný seznam
	int delkaUseku = 1; //délka slévaných úseků
	int pocetPrvku = 0; //počet prvků spojového seznamu, spočte se v první kroku
	PrvekSeznamu *novyZacatek = (PrvekSeznamu *)malloc(sizeof(PrvekSeznamu));
	novyZacatek->dalsi = zacatek;
	PrvekSeznamu *prvek1; //ukazatel na poslední prvek již slité části seznamu
	//při slévání je prvek1 poslední prvek před 1. slévaným úsekem
	PrvekSeznamu *prvek2; //prvek před aktuálně zpracovávaným prvkem
	//prvek2 je poslední prvek před 2. slévaným úsekem
	do { //cyklus dle kroků algoritmu
		prvek1 = novyZacatek; //nastav ukazatele pred zacatek
		prvek2 = novyZacatek;
		do { //cyklus slévání dvou úseků
			int delka1 = delkaUseku; //délka prvního slévaného úseku
			int delka2 = delkaUseku; //délka druhého slévaného úseku
			for (int i = 0; i < delkaUseku; i++) { //projdi první úsek
				prvek2 = prvek2->dalsi;
				if (delkaUseku == 1) pocetPrvku++; //v prvním kroku počítáme prvky
				if (prvek2 == NULL) break; //konec seznamu
			}
			if (prvek2 == NULL) break; //druhy úsek je prázdný, nemá cenu slévat
			//dokud nejsou slity všechny prvky v obou úsecích
			while (delka1 > 0 || (delka2 > 0 && prvek2->dalsi != NULL)) {
				//došly prvky v 2. úseku nebo je 1. prvek 1. úseku starší než 1. prvek 2. úseku
				if (delka2 <= 0 || prvek2->dalsi == NULL
				 || (prvek1->dalsi != NULL
				     && prvek1->dalsi->stari > prvek2->dalsi->stari)) {
					delka1--;
					prvek1 = prvek1->dalsi; //zatřiďujeme prvek z 1. úseku, stačí tedy posunout ukazatel
				}
				else if (delka1 <= 0) { //došly prvky v 1. úseku
					delka2--;
					prvek1 = prvek1->dalsi; //je třeba posunout oba ukazatele
					prvek2 = prvek2->dalsi;
					if (delkaUseku == 1) pocetPrvku++;
				}
				else { //je třeba přehodit 1. prvek 2. úseku před 1. prvek 1. úseku
					PrvekSeznamu *usek1 = prvek1->dalsi;
					prvek1->dalsi = prvek2->dalsi;
					prvek2->dalsi = prvek2->dalsi->dalsi;
					prvek1->dalsi->dalsi = usek1;
					prvek1 = prvek1->dalsi;
					if (delkaUseku == 1) pocetPrvku++;
					delka2--;
				}
			}
			prvek1 = prvek2;
		} while (prvek2->dalsi != NULL); //dokud nejsme na konci seznamu
		delkaUseku = delkaUseku * 2; //zdvojnásob délku slévaných úseků
	} while (delkaUseku < pocetPrvku); //dokud jsme neslili všechny prvky
	return novyZacatek->dalsi;
}


int main(int argc, char *argv[])
{
  int N, a;
  scanf("%d", &N);
  PrvekSeznamu *spojak = NULL, *curr = NULL;
  for (int i = 0; i < N; i++) {
	  PrvekSeznamu *novy = (PrvekSeznamu *)malloc(sizeof(PrvekSeznamu));
	  scanf("%d", &a);
	  novy->stari = a;
	  if (curr != NULL) curr->dalsi = novy;
	  curr = novy;
	  if (spojak == NULL) spojak = curr;
  }
  curr = EWDSort(spojak);
  while (curr != NULL) {
	  printf("%d ", curr->stari);
	  curr = curr->dalsi;
  }
  printf("\n");
  return 0;
}