#include<iostream>
using namespace std;

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

arbore *rad;
int n, x;

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

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

void SS(arbore *&b)
{arbore *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(arbore *&a)
{arbore *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(arbore *&c)
{DD(c->st);
SS(c);
}

void DS(arbore *&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=new arbore;
	 r->st=r->dr=0;
	 r->info=val;
	 r->h=0;
	}
r->h=max(echil(r->st), echil(r->dr))+1;
}

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

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;
}