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

typedef struct Node
{
    int v,h;
    struct Node *l, *r;
    
}Node;
int H(Node* n) { return n?n -> h:0;}
Node* nn(int v)
{
    Node* n=malloc(sizeof(Node));
    n -> v = v; n - h = l; n -> l =n -> r NULL;
    return n;
}
int bal(Node* n) { return H(n -> l)-H(n -> r);}
Node* rotR(Node* y)
{
    Node* x=y->l; Node* t=x->r; x->r=y; y->l=t; y->h=1+(H(y->l)>H(y->r)?H(x->l):H(x->r));
    return x;
}
Node* rotL(Node* x)
{ 
    Node* y=x->r; Node* t=y->l; y->l=x; x->r=t; x->h=1+(H(x->l)>H(x->r)?H(x->l):H(x->r));y->h=1+(H(y->l)>H(y->r)?H(y->l):H(y->r));
    return y;
}
Node*ins(Node* n, int v)
{
    if(!n) return nn(v);
    if(v<n->v) n->l=ins(n->r,v);
    else if(v>n->v) n->r=ins(n->r,v);
    else return n;
    
    n->h=l+(H(n->l)>H(n->r)?H(n->l):H(n->r));
    int b=bal(n);
    if(b>l && v<n->v)return rotR(n);
    if(b<-l && v>n->r->v)return rotL(n);
    if(b>l && v>n->l->v)
    { n->l=rotL(n->l);return rotR(n);}
    if(b<- && v<n->r->v)
    { n->r=rotR(n->r); return rotL(n);}
    
    return n;
}

void ino(Node*r)
{
    if(!r) return;
    ino(r->l);
    printf("%d",r->v);
    ino(r->r);
}

int main()
{
    int n,x;
    if(scanf("%d",&n)!=1 || n<=0)
    {
        printf("invalid input");return 0;}
        Node* root=NULL;
        for(int i=0;i<n;i++)
        {
            if(scanf("%d,&x")!=1 || x<0)
            {
                printf("invalid input");
                return 0;
            }
            root=ins(root,x);
        }
        ino(root);
}
            }
    }
}
}
    
}