#include <cstdio>
#include <cstring>

int inv;

struct tree
{
  int x;
  tree *l, *r, *p;
  inline tree *GetL() { return inv ? r : l; }
  inline tree *GetR() { return inv ? l : r; }
  inline void SetL( tree *x ) { SetP(x), *(inv ? &r : &l) = x; }
  inline void SetR( tree *x ) { SetP(x), *(inv ? &l : &r) = x; }
  inline tree *other( tree *child ) { return l - child + r; }
  inline int invf( tree *child ) { return child == r; }
  inline void ReplaceMe( tree *x ) { (p->r == this ? p->r : p->l) = x, x->p = p; }
  void SetP( tree *t ) { if (t) t->p = this; }
};

const int max_mem = (int)1e6;

tree t[max_mem];
int mpos = 0;

tree *NewTree( int x )
{
  memset(t + mpos, 0, sizeof(tree));
  t[mpos].x = x;
  return t + mpos++;
}

struct SplayTree
{
  tree *root; // fictive

  SplayTree()
  {
    root = NewTree(0);
  }

  void Splay( tree *x )
  {
    tree *y, *z;
    fprintf(stderr, "1 %d %d %d\n", x, x->p, (x->p ? x->p->p : 0));
    while ((y = x->p) != root && (z = y->p) != root)
    {
 //     fprintf(stderr, "1\n");
      inv = y->invf(x); 
      if (y->invf(x) == z->invf(y))
      {
        fprintf(stderr, "zig-zig!\n");
        tree *A = x->GetL(), *B = x->GetR(), *C = y->GetR(), *D = z->GetR();
        z->ReplaceMe(x);
        x->SetR(y), y->SetR(z);
        x->SetL(A), y->SetL(B), z->SetL(C), z->SetR(D);
      }
      else
      {
        fprintf(stderr, "zig-zag!\n");
        tree *A = z->GetL(), *B = x->GetL(), *C = x->GetR(), *D = y->GetR();
        z->ReplaceMe(x);
        x->SetL(z), x->SetR(y);
        z->SetL(A), z->SetR(B), y->SetL(C), y->SetR(D);
      }
    }
    fprintf(stderr, "x=%d root=%d y=%d\n", x, root, y);
    if (y != root)
    {
      z = y->other(x);
      inv = y->invf(x); 
      fprintf(stderr, "z=%d inv=%d\n", z, inv);
      y->ReplaceMe(x);
      fprintf(stderr, "z=%d inv=%d GetR=%d\n", z, inv, x->GetR());
      y->SetL(x->GetR());
      fprintf(stderr, "3\n");
      x->SetR(y);
      fprintf(stderr, "3\n");
    }
    fprintf(stderr, "3\n");
  }

  void Add( int x )
  {
    fprintf(stderr, "Add(%d)\n", x);
    tree **t = &root->l, *last = root;
    while (*t)
    {
      last = *t;
      if ((*t)->x > x)
        t = &(*t)->l;
      else
        t = &(*t)->r;
    }
    fprintf(stderr, "Go Splay()...\n");
    *t = NewTree(x), (*t)->p = last;
    Out();
    fprintf(stderr, "Go Splay()...\n");
    Splay(*t);
  }

  void go( tree *t, int dep )
  {
    if (!t)
      return;
    go(t->l, dep + 1);
    printf("%*sx=%d,[this=%d,p=%d,l=%d,r=%d]\n", dep * 2, "", t->x, (int)t, (int)t->p, (int)t->l, (int)t->r);
    go(t->r, dep + 1);
  }

  void Out()
  {
    fprintf(stderr, "Go Out()...\n");
    if (!root->l)
      puts("<empty_tree>");
    else
      go(root->l, 0);
  }
};

int main()
{
  SplayTree t;
  t.Add(0);
  t.Add(1);
  t.Add(2);
  t.Add(3);
  t.Add(4);
  t.Add(5);
  t.Add(6);
  t.Add(7);
  t.Add(8);
  t.Add(-2);
  t.Add(-1);
  t.Out();
  return 0;
}