#include <iostream>
#include <fstream>
#include<cstring>
#include<cmath>
using namespace std;
struct nod
{
    int x, h, w, c;
    nod *st, *dr;
};
nod *root;
ofstream g("algsort.out");
int height(struct nod *n)
{
    int dr, st;
    if (n->dr==NULL) dr=0;
        else dr=n->dr->h;
    if (n->st==NULL) st=0;
        else st=n->st->h;
    return 1+max(st, dr);
}
int alt(struct nod *n)
{
    int dr, st;
    if (n->dr==NULL) dr=0;
        else dr=n->dr->h;
    if (n->st==NULL) st=0;
        else st=n->st->h;
    return st-dr;
}
int weight(struct nod* n)
{
    if (n->dr==NULL && n->st==NULL) return 1;
    int dr, st;
    if (n->dr==NULL) dr=1;
        else dr=n->dr->w;
    if (n->st==NULL) st=1;
        else st=n->st->w;
    return st+dr+1;
}
struct nod* left_rotate(nod* x)
{
    nod *r;

    r = x->dr;
    x->dr = r->st;
    r->st = x;

    x->h=height(x);
    x->w=weight(x);
    r->w=weight(r);
    r->h=height(r);
    return r;
}
struct nod* right_rotate(nod* x)
{
    nod *l = x->st;
    x->st = l->dr;
    l->dr = x;

    x->h=height(x);
    x->w=weight(x);
    l->w=weight(l);
    l->h=height(l);
    return l;
}

nod* balance(nod* n)
{
    n->h = height(n);
    n->w = weight(n);
    int b = alt(n);
    if (b>1)
    {
        if (alt(n->st)<0)
            n->st = left_rotate(n->st);
        return right_rotate(n);
    }

    if (b<-1)
     {
         if (alt(n->dr)>0)
            n->dr = right_rotate(n->dr);
         return left_rotate(n);
     }
     return n;
}


struct nod* inserare(struct nod *n, int val)
{

    if (n==NULL) {n=new nod; n->x=val; n->h=1; n->w=1; n->st=NULL; n->dr=NULL; n->c=1 ; return n;}
    else
        if (n->x > val) n->st=inserare(n->st, val);
            else if (n->x < val) n->dr=inserare(n->dr, val);
                else n->c++;
    return balance(n);
}
struct nod* cauta(struct nod* n, int val)
{
    if (n==NULL) return NULL;
    if (n->x==val) return n;
        else
        {
            if (n->x>val) return cauta (n->st, val);
            else return cauta(n->dr, val);
        }
}
struct nod* sterge(struct nod *n, int val)
{
    nod *t;
   if (n==NULL) return n;
    if (n->x!=val)
        {
            if (n->x > val) n->st=sterge (n->st, val);
                else n->dr=sterge(n->dr, val);
        }
    else
    if (n->dr==NULL)
        {
            if (n->st==NULL) {t=n->st; return t; }
                else {t=n->st; n=t;}
        }
        else
            if (n->st==NULL) {t=n->dr; n=t;}
                else{
            t=n->dr;
            while(t->st) t=t->st;
            swap(n->x,t->x);
            n->dr=sterge(n->dr, t->x);}
    n->h=height(n);
   return balance(n);
}
void inordine(nod *n)
{
    if (n==NULL) return;
    inordine(n->st);
    while (n->c--) g<<n->x<<' ';
    inordine(n->dr);
}
void kelement(nod* n, int k)
{
    if (n==NULL) return;
    if (weight(n->st)==k-1) {g<<n->x<<'\n'; return;}
        else if (weight(n->st)<k-1) kelement(n->st, k);
                else kelement(n->dr, k);
}
int main()
{
    int n, nr, i, j, x;
    ifstream f("algsort.in");
    f>>n;
    root=new nod;
    root=NULL;
    for (i=1;i<=n;i++)
    {
        f>>x;
        root=inserare(root, x);
    }
    inordine(root);
    g<<'\n';
}