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

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

nod *rad;
long n, x;

void afisare_SRD(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_SRD(rad);
return 0;
}

void afisare_SRD(nod *r)
{if(r)
   {afisare_SRD(r->st);
    for(; r->k; (r->k)--)
       printf("%d ", r->info);
	afisare_SRD(r->dr);
   }
}

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=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=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)
      {(r->k)++;
       return;
      }
    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=new nod;
	 r->st=r->dr=0;
	 r->info=val;
	 r->h=0;
	 r->k=1;
	}
r->h=max(echil(r->st), echil(r->dr))+1;
}