#include<stdio.h>
#include<stdlib.h>
typedef struct N{int k,h;struct N*l,*r;}N;
int H(N*n){return n?n->h:0;}
int M(int a,int b){
    return a>b?a:b;}
    N*nn(int k)
    {N*n=malloc(sizeof(N));n->k=k;n->l=n->r=NULL;
    n->h=1;return n;
N*rr(N*y){
    N*x=y->l;y->l=x->r;x->r=y;
    y->h=M(H(y->l),H(y->r))+1;
    x->h=M(H(x->l),H(x->r))+1;
    return x;
}
N*lr(N*x){
    N*y=x->r; x->r=y->l; y->l=x;
    x->h=M(H(x->l),H(x->r))+1;
    y->h=M(H(y->l),H(y->r))+1;
    return y;
}
int B(N*n){return H(n->l)-H(n->r);}
N*ins(N*n,int k){
    if(!n)return nn(k);
    if(k<n->k) n->l=ins(n->l,k);
    else n->r=ins(n->r,k);
    n->h=1+M(H(n->l),H(n->r));
    int b=B(n);
    if(b>1&&k<n->l->k)return rr(n);
    if(b<-1&&k>n->r->k)return lr(n);
    if(b>1&&k>n->l->k){n->l=lr(n->l);return rr(n);
}
    if(b<-1&&k<n->r->k){n->r=rr(n->r);return lr(n);
}
return n;
}
void invalid(N*n){
    if(n){invalid(n->l);
printf("%d",n->k);invalid(n->r);}}
int main(){
    int n,x;
    if(scanf("%d",&n)!=1||n<0)
    {
        printf("Invalid input");
        return 0;
        
    }
        N*r=0;
        for(int i=0;i<n;i++){
            if(scanf("%d",&x)!=1||x<-1000||x>1000)
            {
             printf("Invalid input");
        return 0;
                
            }
        r=ins(r,x);
  }
        invalid(r);
}}