#include <cstdio>
#include <cassert>
#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) { size = 1 + l->size + r->size; }

  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);
  }

  void check()
  {
    if (this == null)
      return;
    l->check();
    assert(size == 1 + l->size + r->size);
    r->check();
  }

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

typedef T *Node;

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

Node Insert( Node v, int x )
{
  Node p;
  if (v == z)
    p = new T(x, z, z);
  else if (v->x > x)
    p = new T(v->x, Insert(v->l, x), v->r);
  else
    p = new T(v->x, v->l, Insert(v->r, x));
  return p->balance();
}

// [2, 3, 4, 5, 2, 3, 4, 5]
// Insert(0, 7)
// [7, 2, 3, 4, 5, 2, 3, 4, 5]
// Insert(2, 10)
// [7, 2, 10, 3, 4, 5, 2, 3, 4, 5]
Node Insert( Node v, int i, int x )  
{
  Node p;
  if (v == z)
    p = new T(x, z, z);
  else if (i < v->l->size + 1) // <-------------- 1
    p = new T(v->x, Insert(v->l, i, x), v->r);
  else
    p = new T(v->x, v->l, Insert(v->r, i - (v->l->size + 1), x)); // <-------------- 2
  return p->balance();
}


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