#include <cstdio>
#include <algorithm>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

struct T
{
  static T *null;
  int x, size;
  T *l, *r;

  T() { l = r = this, size = 0; }
  T( int x, T *l, T *r ) : x(x), l(l), r(r) { calc(); }
  void calc() { size = l->size + r->size + (this != null); }

  void out( int dep = 0 )
  {
    if (this == null)
      return;
    l->out(dep + 1);
    printf("%*s%d, size=%d\n", 2 * dep, "", x, size);
    r->out(dep + 1);
  }

  T* balance()
  {
    if (l->l->size > r->size) return rotateLeft();
    if (r->r->size > l->size) return rotateRight();
    return this;
  }

  T* rotateLeft()
  {
    T* p = l;
    l = p->r, p->r = this;
    p->r->calc(), p->calc();
    return p;
  }

  T* rotateRight()
  {
    T* p = r;
    r = p->l, p->l = this;
    p->l->calc(), p->calc();
    return p;
  }
};

typedef T *Node;

Node T::null = new T();
Node z = T::null, root = z;

void Insert( Node &v, int x )
{
  if (v == z)
    v = new T(x, z, z);
  else
    Insert(v->x > x ? v->l : v->r, x);
  v = v->balance();
  v->calc();
}

int main()
{
  const int n = 10;
  forn(i, n)
    Insert(root, i);
  forn(i, n)
    Insert(root, 2 * n - i);
  root->out();
  return 0;
}