#define pragma -O3
using namespace std;
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#define rnd (rand()-1)
#define oo 0x3f3f3f3f
struct nod { int v, p;nod *s, *d;};
nod *r, *nil;

void init()
{
	srand(time(0));
	r=nil=new nod;
	nil->v=nil->p=-oo;
	nil->s=nil->d=0;
}
inline void rots(nod*&n)
{
	nod *t=n->s;
	n->s=t->d;
	t->d=n;
	n=t;
}

inline void rotd(nod*&n)
{
	nod *t=n->d;
	n->d=t->s;
	t->s=n;
	n=t;
}


void insert(nod *&n, int v)
{
	if(n==nil)
	{
		n=new nod;
		n->v=v;n->p=rnd;
		n->s=n->d=nil;
		return ;
	}
	
	if(n->v>v) 
	{
		insert(n->s, v);
		if(n->s->p>n->p) rots(n);
	}
	if(n->v<v)
	{
		insert(n->d, v);
		if(n->d->p>n->p) rotd(n);
	}
}


int find(nod *&n, int v)
{
	if(n==nil) return 0;
	if(n->v==v) return 1;
	if(n->v>v) return find(n->s, v);
	return find(n->d, v);
}

int nrmax;
void ino(nod*&n, int nr)
{
	if(n==nil) return;
	ino(n->s, nr+1);
	if(nr>nrmax) nrmax=nr;
	ino(n->d, nr+1);
}

int x[1<<20], n;
int main()
{
	init();
	insert(r, 23);
	insert(r, 11);
	insert(r, 56);
	insert(r, 9);
	
//	printf("\n");
	int t;
	double s=clock();
	n=1000000;
//	for(int i=1;i<=n;++i) x[i]=i;
	//random_shuffle(x+1, x+n+1);
	for(int i=1;i<=n;++i)
	{
		//t=i;
		t=rnd;
	//	if(!find(r, t))
	insert(r, t);
	}
	
	double e=clock();
	printf("%f\n",(e-s)/(double)CLOCKS_PER_SEC); 
	
	ino(r,1);
	//printf("%d\n", nrmax);
	return 0;
}