//Sortare cu AVL - Moartea Frantei :))

#include<stdio.h>
#include<stdlib.h>

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

FILE *g = fopen("algsort.out","w");

class AVL
{

private:

    nod *rad;
    int size;

    int maxInt(int a,int b)
    {
        return a > b ? a : b;
    }

    int max(nod *a,nod *b)
    {
        int Max = 0;

        Max = a ? a->h : 0;
        Max = b ? maxInt(Max,b->h) : Max;

        return Max;
    }

    int abs(int a)
    {
        if(a < 0)
            return -a;
        return a;
    }

    void creare_nod(nod *&rad)
    {
        rad = new nod;
        rad->dr = rad->st = NULL;
        rad->h = 1;
    }

    void rotire_dreapta(nod *&rad)
    {
        nod *fiu = rad->st;
        rad->st = fiu->dr; 
        fiu->dr = rad; 
        rad = fiu;
    }

    void rotire_stanga(nod *&rad)
    {
        nod *fiu = rad->dr;
        rad->dr = fiu->st; 
        fiu->st = rad;
        rad = fiu;
    }

    int get_h(nod *&rad)
    {
        if(!rad)
            return 0;
        return rad->h;
    }

    int get_echilibru(nod *&rad)
    {
        if(!rad)
            return 0;

        return get_h(rad->dr)-get_h(rad->st);
    }

    void echilibreaza(nod *&rad)
    {
        int echilibru = get_echilibru(rad);

        if(abs(echilibru) < 2)
            return ;

        if(echilibru == 2)
        {
            if(get_echilibru(rad->dr) == 1)
                rotire_stanga(rad);
            else
            {
                rotire_dreapta(rad->dr);
                rotire_stanga(rad);
            }
        }
        else
        {
            if(get_echilibru(rad->st) == -1)
                rotire_dreapta(rad);
            else
            {
                rotire_stanga(rad->st);
                rotire_dreapta(rad);
            }
        }

        rad->st->h = max(rad->st->st,rad->st->dr)+1;
        rad->dr->h = max(rad->dr->st,rad->dr->dr)+1; 
        rad->h = max(rad->st,rad->dr)+1;
    }

    void insereaza(nod *& rad,int a)
    {
         if(!rad)
         {
             creare_nod(rad);
             rad->info = a;
             return ;
         }

         if(rad->info <= a)
             insereaza(rad->dr,a);
         else
             insereaza(rad->st,a);

         rad->h = max(rad->st,rad->dr)+1;
         echilibreaza(rad);
    }

    int search(nod *rad,int a)
    {
        if(!rad)
            return 0;

        if(rad->info == a)
            return 1;

        if(rad->info > a)
            return search(rad->st,a);
        else 
            return search(rad->dr,a);
    }

    int maximul(nod *rad)
    {
        if(!rad)
            return 0;
        if(rad->dr)
            return maximul(rad->dr);
        return rad->info;
    }

    int deleteMax(nod *&rad)
    {
        int p;

        if(!rad->dr)
        {
            p = rad->info;
            rad = rad->st;
            if(rad)
                rad->h = max(rad->st,rad->dr)+1;
            return p;
        }

        p = deleteMax(rad->dr);
        rad->h = max(rad->st,rad->dr)+1;
        return p;
    }

    void stergeVal(nod *&rad)
    {
        nod *p;

        if(!rad->st && !rad->dr)
        {
            delete rad;
            rad = NULL;
            return ;
        }

        if(!rad->st)
        {
            p = rad->dr;
            delete rad;
            rad = p;
            return ;
        }

        if(!rad->dr)
        {
            p = rad->st;
            delete rad;
            rad = p;
            return ;
        }

        rad->info = deleteMax(rad->st);
    }

    void deleteVal(nod *&rad,int a)
    {
        if(rad->info == a)
            stergeVal(rad);
        else if(rad->info > a)
            deleteVal(rad->st,a);
        else
            deleteVal(rad->dr,a);

        if(!rad)
            return ;

        rad->h = max(rad->st,rad->dr)+1;
        echilibreaza(rad);
    }

    void SRD(nod *rad)
    {
        if(!rad)
            return ;

        SRD(rad->st);
        printf("%d -> h = %d\n",rad->info,rad->h);
        SRD(rad->dr);
    }

    void RSD(nod *rad)
    {
        if(!rad)
            return ;

        printf("%d -> h = %d\n",rad->info,rad->h);
        RSD(rad->st);
        RSD(rad->dr);
    }

    void SDR(nod *rad)
    {
        if(!rad)
            return ;

        SDR(rad->st);
        SDR(rad->dr);
        printf("%d -> h = %d\n",rad->info,rad->h);
    }

    void afisareF(nod *rad)
    {
        if(!rad)
            return ;
        
        afisareF(rad->st);
        fprintf(g,"%d ",rad->info);
        afisareF(rad->dr);
    }

public:
    
    AVL(void)
    {
        rad = NULL;
        size = 0;
    }

    void adauga(int a)
    {
       insereaza(rad,a);
       ++ size;
    }

    void afisareSRD(void)
    {
        printf("Dimensiunea : %d\n\n",size);
        SRD(rad);
        printf("\n");
    }

    void afisareRSD(void)
    {
        printf("Dimensiunea : %d\n\n",size);
        RSD(rad);
        printf("\n");
    }

    void afisareSDR(void)
    {
        printf("Dimensiunea : %d\n\n",size);
        SDR(rad);
        printf("\n");
    }

    int cauta(int a)
    {
        return search(rad,a);
    }

    void afiseaza(void)
    {
        printf("Dimensiunea : %d\n\n",size);
        SRD(rad);
        printf("\n");
    }

    int maxim(void)
    {
        return maximul(rad);
    }

    void sterge(int a)
    {
        if(!search(rad,a))
            return ;
        deleteVal(rad,a);
        -- size;
    }

    void afisareFisier(void)
    {
        afisareF(rad);
    }

};

AVL Q;

FILE *f = fopen("algsort.in","r");

int N;

void citire(void)
{
    int a;

    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%d",&a);
        Q.adauga(a);
    }
}

int main()
{
    citire();
    Q.afisareFisier();
}