//(c) Mircea Dima
//AVL
using namespace std;
#include <cstdio>
#include <algorithm>
#include <set>
struct nod { int v, h; nod *l, *r;};

typedef nod* tree;

tree R, nil;

inline void init()
{
	nil=new nod;
	nil->l=nil->r=0;
	nil->v=nil->h=0;
	R=nil;
}

inline void geth(tree &n)
{
	if(n == nil) return;
	n->h=max(n->l->h, n->r->h)+1;
}

inline void rotl(tree &n)
{
	tree t=n->l;
	n->l=t->r;
	t->r=n;
	geth(n); geth(t);
	n=t;
}

inline void rotr(tree &n)
{
	tree t=n->r;
	n->r=t->l;
	t->l=n;
	geth(n);geth(t);
	n=t;
}

inline void balance(tree &n)
{
	geth(n);
	
	if(n->l->h > n->r->h+1)
	{
		if(n->l->r->h > n->l->l->h) rotr(n->l);
		rotl(n);
	}
	else
	if(n->r->h > n->l->h+1)
	{
		if(n->r->l->h > n->r->r->h) rotl(n->r);
		rotr(n);
	}
}

inline void insert(tree &n, int v)
{
	if(n == nil)
	{
		n=new nod;
		n->l=n->r=nil;
		n->v=v;
		n->h=1;
		return;
	}
	
	if(v < n->v) insert(n->l, v);
	if(v > n->v) insert(n->r, v);
	
	balance(n);
}

tree erase(tree &n, int v)
{
	tree t;
	if(n == nil) return n;
	if(v < n->v) n->l=erase(n->l,v);
	if(v > n->v) n->r=erase(n->r,v);
	

	if(v == n->v)
	{
		if(n->l == nil || n->r == nil)
		{
			if(n->l == nil) t=n->r;
			else t=n->l;
			free(n);
			return t;
		}
		else
		{
			for(t=n->r; t->l != nil; t=t->l);
			n->v=t->v;
			n->r=erase(n->r,t->v);
			balance(n);
			return n;
		}
	}

	balance(n);
	return n;
}


inline int find(tree n, int v)
{
	if(n == nil) return 0;
	if(v < n->v) return find(n->l,v);
	if(v > n->v) return find(n->r,v);
	return 1;
}

inline void ino(tree n)
{
	if(n == nil) return;
	
	ino(n->l);
	printf("(%d ", n->v);
	ino(n->r);
}

inline void afis(tree n)
{
	ino(n);
	printf("\n");
}


inline int max_height(tree n)
{
	if(n == nil) return 0;
	return max(max_height(n->l), max_height(n->r))+1;
}

int main()
{
	init();
		
	insert(R, 9);
	insert(R, 13);
	insert(R, 5);
	insert(R, 20);
	insert(R, 32);
	insert(R, 12);
	insert(R, 1);
	insert(R, 10);
	R=erase(R,32);
	afis(R);
	
	
	srand(time(0));
	double s=clock();
	
	int i, n=1000000;
	set<int>A;
	//for(i=1;i<=n;++i) A.insert((rand()*rand())%100000000);
	for(i=1;i<=n;++i) insert(R, (rand()*rand())%100000000);
	//for(i=1;i<=n;++i) R=erase(R, rand()*rand());
	//for(i=1;i<=n;++i) find(R, rand()*rand());
	printf("%lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
		
	printf("%d\n", max_height(R));
	return 0;
}