#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
const int N = 500010;
ifstream F("algsort.in");
ofstream G("algsort.out");
struct item {
int key;
char pr;
item *l , *r;
item() {
}
item(int k) {
key = k;
pr = (rand() << 3) ^ rand();
l = r = NULL;
}
};
#define tree item*
void split(tree t,int key,tree &l,tree &r)
{
if ( !t )
{
l = r = NULL;
}
else
if ( key < t->key )
{
split(t->l,key,l,t->l);
r = t;
}
else
{
split(t->r,key,t->r,r);
l = t;
}
}
void insert(tree& t,tree x)
{
if ( !t )
t = x;
else
if ( x->pr > t->pr )
{
split(t,x->key,x->l,x->r); // taie t in copii lui x
t = x;
}
else
{
if ( x->key < t->key ) // ma uit in care fiu il pun
insert( t->l , x );
else
insert( t->r , x );
}
}
void merge(tree& t,tree l,tree r)
{
if ( !l || !r )
t = l ? l : r;
else
if ( l->pr > r->pr )
{
merge(l->r,l->r,r); // unesc fiul drept ai lui l cu right
t = l;
}
else
{
merge(r->l,l,r->l);
t = r;
}
}
void erase(tree &t,int key)
{
if ( t->key == key )
merge(t,t->l,t->r);
else
{
if ( key < t->key )
erase(t->l,key);
else
erase(t->r,key);
}
}
int co = 0;
int n,a,b;
void print(tree t)
{
if ( t->l != NULL )
print(t->l);
G<<t->key<<' ';
if ( t->r != NULL )
print(t->r);
}
tree t = NULL;
const int sz = 500010;
int main()
{
srand(time(0));
F>>n;
for (int i=1,x;i<=n;++i)
{
F>>x;
tree q = new item(x);
insert(t,q);
//printd(t); cerr<<'\n';
}
print(t);
G<<'\n';
}