using namespace std;
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define oo 0x3f3f3f3f

struct node { int v, p, h; node *left, *right;};

typedef node* treap;

treap R, nil;

inline void init(treap &R)//trebuie apelata la inceput in main
{
	srand(time(0));
	nil=new node;
	nil->left=nil->right=0;
	nil->v=nil->p=-oo;
	nil->h=0;
	R=nil;
}

inline void geth(treap &n)
{
	if(n==nil)return;
	n->h=1;
	if(n->left) n->h += n->left->h;
	if(n->right) n->h += n->right->h;
}

inline void rotleft(treap &n)
{
	treap t=n->left;
	n->left=t->right;
	t->right=n;
	geth(n); geth(t);
	n=t;
}

inline void rotright(treap &n)
{
	treap t=n->right;
	n->right=t->left;
	t->left=n;
	geth(n); geth(t);
	n=t;
}

inline void insert(treap &n, int v){
	if(n == nil){
		n= new node;
		n->v=v;
		n->p=rand();
		n->left=n->right=nil;
		n->h=1;
		return;
	}
		
	if(v < n->v){
		insert(n->left, v);
		if(n->left->p > n->p) rotleft(n);
	}
	
	if(v > n->v){
		insert(n->right, v);
		if(n->right->p > n->p) rotright(n);
	}
	
	geth(n);
}

inline void sterge(treap &n, int v)
{
	if(n == nil) return;
	if(v < n->v) sterge(n->left, v);
	if(v > n->v) sterge(n->right, v);
	if(v == n->v){
		if(n->left->p > n->right->p) rotleft(n);
		else rotright(n);
		
		if(n != nil) sterge(n, v);
		else{
			free(n->left);
			n->left=0;
		}
	}
	geth(n);
}

inline void ino(treap n){
	if(n == nil) return;
	ino(n->left);
	printf("%d ", n->v);
	ino(n->right);
}

inline int findk(treap n, int k){
	if(n == nil) return 0;
	if(n->left->h +1 == k) return n->v;
	if(n->left->h +1 < k) return findk(n->right, k - (n->left->h+1) );
	if(n->left->h + 1> k) return findk(n->left, k);
	return 0;
}


inline int max_height(treap n)
{
	if(n == nil) return 0;
	return max(max_height(n->left), max_height(n->right))+1;
}


int a[1000001];

int main(){
	init(R);
	/*
	insert(R, 12);
	insert(R, 8);
	insert(R, 9);
	insert(R, 4);
	insert(R, 10);
	insert(R, 19);
	
	
	sterge(R, 10);
	sterge(R, 8);
	insert(R, 23);
	insert(R, 12);
	insert(R, 43);\n
	sterge(R, 19);
	
	ino(R);
	printf("\n");
	
	printf("%d %d %d %d %d\n", findk(R,1), findk(R,2), findk(R,3), findk(R, 4), findk(R,5));
	*/
	int n=1000000;
	int i;
	for(i=1;i<=n;++i) a[i]=(rand()*rand())%100000000;
	
	printf("%d %d\n", a[1],a[2]);
	double start=clock();
	
	for(i=1;i<=n;++i) insert(R, a[i]);
//	for(i=1;i<=n;++i) printf("%d ", findk(R, i));
	printf("\n\n");
	//ino(R);
	
	///for(i=1;i<=n;++i) sterge(R, a[i]);
	
//	ino(R);
	
	
	
	printf("\n\n%lf\n", (clock()-start)/(double)CLOCKS_PER_SEC);

	printf("%d\n", max_height(R));
	return 0;
}