#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; }
  inline 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;
    while ((y = x->p) != root && (z = y->p) != root)
    {
      inv = y->invf(x); 
      if (y->invf(x) == z->invf(y))
      {
        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
      {
        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);
      }
    }
    if (y != root)
    {
      z = y->other(x);
      inv = y->invf(x); 
      y->ReplaceMe(x);
      y->SetL(x->GetR()), x->SetR(y);
    }
  }

  void Add( int x )
  {
    tree **t = &root->l, *last = root;
    while (*t)
    {
      last = *t;
      if ((*t)->x > x)
        t = &(*t)->l;
      else
        t = &(*t)->r;
    }
    *t = NewTree(x), (*t)->p = last;
    Splay(*t);
  }
};