#include <stdio.h>
#include <stdlib.h>
#define SOUBOR_VSTUP "pocitace.in"

typedef struct vrchol {
    int typ;
    int pocet;
    vrchol *levy;
    vrchol *pravy;
    vrchol *otec;
    char vyvazenost;
} vrchol;

vrchol *koren=NULL;

// --- začátek části starající se o AVL stromy ---
    // rotace doprava
    void rotaceRR(vrchol *aktualni) {
        vrchol *pomocny=aktualni->levy;
        aktualni->levy=pomocny->pravy;
        pomocny->pravy=aktualni;
        aktualni->vyvazenost=0;
        pomocny->vyvazenost=0;
        // a teď přepojíme otce, pokud ho vrchol má
        if(aktualni->otec==NULL) koren=pomocny;
        else if(aktualni->otec->levy==aktualni) aktualni->otec->levy=pomocny;
        else aktualni->otec->pravy=pomocny;
    }
    // rotace doleva
    void rotaceLL(vrchol *aktualni) {
        vrchol *pomocny=aktualni->pravy;
        aktualni->pravy=pomocny->levy;
        pomocny->levy=aktualni;
        aktualni->vyvazenost=0;
        pomocny->vyvazenost=0;
        // a teď přepojíme otce, pokud ho vrchol má
        if(aktualni->otec==NULL) koren=pomocny;
        else if(aktualni->otec->levy==aktualni) aktualni->otec->levy=pomocny;
        else aktualni->otec->pravy=pomocny;
    }
    // dvojrotace doleva-doprava
    void rotaceLR(vrchol *aktualni) {
        vrchol *pomocny=aktualni->levy->pravy;
        aktualni->levy->pravy=pomocny->levy;
        pomocny->levy=aktualni->levy;
        aktualni->levy=pomocny->pravy;
        pomocny->pravy=aktualni;
        // teď podle původního stavu vnuka nastavíme vyváženost
        if(pomocny->vyvazenost==-1) {
            pomocny->levy->vyvazenost=0;
            pomocny->pravy->vyvazenost=1;
        } else {
            pomocny->levy->vyvazenost=-1;
            pomocny->pravy->vyvazenost=0;
        }
        pomocny->vyvazenost=0; // kořen rotace je vždy vyvážen
        // a teď přepojíme otce, pokud ho vrchol má
        if(aktualni->otec==NULL) koren=pomocny;
        else if(aktualni->otec->levy==aktualni) aktualni->otec->levy=pomocny;
        else aktualni->otec->pravy=pomocny;
    }
    // dvojrotace doprava-doleva
    void rotaceRL(vrchol *aktualni) {
        vrchol *pomocny=aktualni->pravy->levy;
        aktualni->pravy->levy=pomocny->pravy;
        pomocny->pravy=aktualni->pravy;
        aktualni->pravy=pomocny->levy;
        pomocny->levy=aktualni;
        // teď podle původního stavu vnuka nastavíme vyváženost
        if(pomocny->vyvazenost==-1) {
            pomocny->levy->vyvazenost=0;
            pomocny->pravy->vyvazenost=1;
        } else {
            pomocny->levy->vyvazenost=-1;
            pomocny->pravy->vyvazenost=0;
        }
        pomocny->vyvazenost=0; // kořen rotace je vždy vyvážen
        // a teď přepojíme otce, pokud ho vrchol má
        if(aktualni->otec==NULL) koren=pomocny;
        else if(aktualni->otec->levy==aktualni) aktualni->otec->levy=pomocny;
        else aktualni->otec->pravy=pomocny;
    }

    void zkontroluj_vyvazenost(vrchol *aktualni) {
        if(aktualni->vyvazenost==-2 && aktualni->levy->vyvazenost==-1) rotaceRR(aktualni);
        else if(aktualni->vyvazenost==-2 && aktualni->levy->vyvazenost==1) rotaceLR(aktualni);
        else if(aktualni->vyvazenost==2 && aktualni->pravy->vyvazenost==1) rotaceLL(aktualni);
        else if(aktualni->vyvazenost==2 && aktualni->pravy->vyvazenost==-1) rotaceRL(aktualni);
	// nebo pokud nenastala rotace, přepošleme nevyváženost o úroveň výš (pokud to není kořen)
        else if(aktualni->otec!=NULL) {
            if(aktualni->otec->levy==aktualni) aktualni->otec->vyvazenost--;
            else aktualni->otec->vyvazenost++;
            zkontroluj_vyvazenost(aktualni->otec);
        }
    }
// --- konec části starající se o AVL stromy ---

void zaloz_vrchol(vrchol *otec,int typ,bool levy=true) {
    vrchol *pomocny=(vrchol *) malloc(sizeof(vrchol));
    pomocny->typ=typ;
    pomocny->pocet=1;
    pomocny->levy=NULL;
    pomocny->pravy=NULL;
    pomocny->vyvazenost=0;
    pomocny->otec=otec;
    if(otec==NULL) koren=pomocny;
    else if(levy) {
        otec->levy=pomocny;
        otec->vyvazenost--;
        zkontroluj_vyvazenost(otec);
    } else {
        otec->pravy=pomocny;
        otec->vyvazenost++;
        zkontroluj_vyvazenost(otec);
    }
}

void pridej_pocitac(int typ) {
    if(koren==NULL) { zaloz_vrchol(NULL,typ); return; }
    vrchol *aktualni=koren;
    while(aktualni->typ!=typ) {
        // procházíme, dokud nenarazíme na hledaný vrchol nebo neexistujícího syna (v takovém případě syna přidáme)
        if(typ<aktualni->typ && aktualni->levy==NULL) { zaloz_vrchol(aktualni,typ,true); return; }
        else if(typ>aktualni->typ && aktualni->pravy==NULL) { zaloz_vrchol(aktualni,typ,false); return; }
        else if(typ<aktualni->typ) aktualni=aktualni->levy;
        else aktualni=aktualni->pravy;
    }
    aktualni->pocet++;
}

void vypis_strom(vrchol *aktualni) {
    if(aktualni->levy!=NULL) vypis_strom(aktualni->levy);
    for(int i=1;i<=aktualni->pocet;i++) printf("%d ",aktualni->typ);
    if(aktualni->pravy!=NULL) vypis_strom(aktualni->pravy);
}

int main() {
    FILE *vstup=fopen(SOUBOR_VSTUP, "r");
    int N;
    fscanf(vstup,"%d",&N);
    for(int i=1;i<=N;i++) {
        int pomocna;
        fscanf(vstup,"%d",&pomocna);
        pridej_pocitac(pomocna);
    }
    vypis_strom(koren);

    return 0;
}