#include<stdio.h>
#include<stdlib.h>
#include<cstdlib>
#include<iostream>
using namespace std;

typedef struct nod{
int info, h; 
nod *st, *dr;
}nod;

nod *rad;
int n, x;

void afisare(nod *r);
int max(int a, int b);
int echil(nod *r); 
void SS(nod *&b);
void DD(nod *&a);
void SD(nod *&c);
void DS(nod *&c);
void adauga(nod *&r, int val);

int main()
{freopen("algsort.in", "r", stdin);
freopen("algsort.out", "w", stdout);
scanf("%d", &n);

for(; n--;)
   {scanf("%d", &x);
    adauga(rad, x);
   }

afisare(rad);
return 0;
}

void afisare(nod *r)
{nod *i=(nod*)malloc(sizeof(nod));
nod *temp=(nod*)malloc(sizeof(nod));     
for(i=rad; i!=0; i=i->dr) 
   {while(i->st!=0) 
         {nod *temp=(nod*)malloc(sizeof(nod));  
          temp=i->st;
          i->st=i->st->dr;
          temp->dr=i;
          i=temp;
         }
    free(temp);
    printf("%d ", i->info);
   }      
}

int max(int a, int b) 
{if(a>=b) return a;
return b;
}

int echil(nod *r)
{if(r==NULL)
   return -1;
return r->h;
}

void SS(nod *&b)
{nod *a=(nod*)malloc(sizeof(nod));
a=b->st;
b->st=a->dr;
a->dr=b;
b->h=max(echil(b->st), echil(b->dr))+1;
a->h=max(echil(a->st), echil(b->dr))+1;
b=a;
}

void DD(nod *&a)
{nod *b=(nod*)malloc(sizeof(nod));
b=a->dr;
a->dr=b->st;
b->st=a;
a->h=max(echil(a->st), echil(a->dr))+1;
b->h=max(echil(b->dr), echil(a->st))+1;
a=b;
}

void SD(nod *&c)
{DD(c->st);
SS(c);
}

void DS(nod *&c)
{SS(c->dr);
DD(c);
}

void adauga(nod *&r, int val)
{if(r)
   {if(val<=r->info)
	  {adauga(r->st, val);
	   if(echil(r->st)-echil(r->dr)==2)
	     {if(val<=r->st->info)
	       SS(r);        
          else SD(r);
         }
      }
	else {adauga(r->dr, val);
	      if(echil(r->dr)-echil(r->st)==2)
	        {if(val>r->dr->info)
               DD(r);   
             else DS(r);
            }
         }
	}
else{r=(nod*)malloc(sizeof(nod));
	 r->st=r->dr=0;
	 r->info=val;
	 r->h=0;
	}
r->h=max(echil(r->st), echil(r->dr))+1;
}