#include <cstdio>

struct T;
typedef T *Node;
int getSize( Node p );

struct T
{
  T *l, *r;
  int x, size;
  T( int x, T *l = 0, T *r = 0 ) : l(l), r(r), x(x) { calc(this); }
};

int getSize( Node p ) { return p ? p->size : 0; }
void calc( Node p ) { if (p) p->size = 1 + getSize(p->l) + getSize(p->r); }

Node Root = 0;

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

Node InsertPersistent( Node p, int x )
{ 
  Node res;
  if (!p)
    res = new T(x);
  else if (x < p->x)
    res = new T(p->x, InsertPersistent(p->l, x), p->r);
  else
    res = new T(p->x, p->l, InsertPersistent(p->r, x));

  if (max(getSize(p->l->l), getSize(p->l->r)) > 2 * getSize(p->r))
    res = RotateLeft(p); // p->l
  return res;
}

Node Rotate( Node p )
{
  // ((p->l->l, p->l->r), p->r) ---> (p->l->l, (p->l->r, p->r))
  return new Node(p->l->x, p->l->l, new Node(p->x, p->l->r, p->r));
}

int main()
{
  vector <Node> roots;
  Node root = 0;
  forn(i, 1e6) // N = 1e6 => NlogN of memory
  {
    roots.push_back(root);
    root = InsertPersistent(root, i); // + log vertices
  }
  // roots[i] = [0..i)
}