/* This program repeatedly inserts n random numbers into
   the root of a BST. Then it traverse the tree
   in in-order to store the keys into array a.
   After the traversal, sorted numbers are in array b. */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define nil 0
#define L 0
#define R 1
int x, k=1, m;
struct item *proot;
struct item *proot1;
struct item{
  int key; struct item *left; struct item *right; int label;
};
int a[100000]; struct item b[100000], *path[100], *u, *v, *w; 
struct item *p, *q, *s, *g, *s1, *g1;
insert(int x){
  int i;
  s=nil; g=nil; s1=nil; g1=nil; p=proot;
  while(p!=nil){
    q=p;
    m++; path[m]=p;  // path keeps track of path to insertion point
    if (x<=(*p).key) {p=p->left;  if(p!=nil)(p->label)=L;}
               else  {p=p->right; if(p!=nil)(p->label)=R;} 
  }
  w=malloc(sizeof(struct item)); path[m+1]=w; // w dummy address
  if(x<=(*q).key){path[m]->left=path[m+1];  g=q; path[m+1]->label=0;} 
    else         {path[m]->right=path[m+1]; s=q; path[m+1]->label=1;}
  i=m+1; 
  while(i>=3){ // back track on the path
    u=path[i-2]; v=path[i-1]; w=path[i]; 
    if(v->label==L){g1=g; g=u;}                              //case 1
    if((v->label==L)&&(w->label==R)){(*u).left=g1;  s1=s;}   //case 2
    if(v->label==R){s1=s; s=u;}                              //case 3
    if((v->label==R)&&(w->label==L)){(*u).right=s1; g1=g;}   //case 4
    i=i-1;
  }
  if(x<=path[m]->key)path[m]->left=nil; else path[m]->right=nil;
  proot=malloc(sizeof(struct item));
  proot->key=x; proot->left=s; proot->right=g;
}
traverse(struct item *proot)
{ struct item *p;
  p=proot;
  if (p!=nil){
    printf("("); // remove this for time measurement
    traverse(p->left);
    b[k]=*p;
    printf("%d", b[k].key); // remove this for time measurement
    k++;
    traverse(p->right); 
    printf(")"); // remove this for time measurement
  }
}
main()
{
  int i,n,t;
  scanf("%d",&n);
  //for(i=1;i<=n;i++) a[i]=random()%100;
  //for (i=1;i<=n;i++)printf("%d ",a[i]); printf("\n");
  //printf("\n");
  for(i=1;i<=n;i++) scanf("%d",&a[i]);
  //getchar();
  for (i=1;i<=n;i++)printf("%d ",a[i]); printf("\n");
  printf("\n");
  t=clock();
  proot=malloc(sizeof(struct item));
  (*proot).key=a[1]; (*proot).left=nil; (*proot).right=nil;
  path[1]=proot;
  for (i=2;i<=n;i++){m=0; insert(a[i]);
  }
  printf("insert complete\n");
  traverse(proot);
  printf("\n");
  printf("time= %d millisec\n\n", (clock()-t)/1000);
}