#include <cstdio>
#include <cstdlib>
#include <ctime>


struct nod { int v, p,h; nod *l, *r;};

typedef nod* treap;

treap R, nil;

inline void init(treap &R)
{
	srand(time(0));
	nil=new nod;
	nil->l=nil->r=0;
	nil->p=nil->v=-0x3f3f3f3f;
	nil->h=0;
	R=nil;
}

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

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

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

inline void insert(treap &n,int v)
{
	if(n == nil)
	{
		n=new nod;
		n->v=v;
		n->p=rand();
		n->l=n->r=nil;
		return;
	}

	if(v < n->v) 
	{
		insert(n->l, v);
		if(n->l->p > n->p) rotl(n);
	}
	if(v > n->v)
	{
		insert(n->r, v); 
		if(n->r->p > n->p) rotr(n);
	}
	geth(n);
}

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

inline int find(treap 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 sterge(treap &n, int v)
{
	if(n == nil) return;
	if(v < n->v) sterge(n->l, v);
	if(v > n->v) sterge(n->r, v);
	if(v == n->v)
	{
		if(n->l->p > n->r->p) rotl(n);
		else rotr(n);

		if(n!=nil) sterge(n, v);
		else
		{
			free(n->l);
			n->l=0;
		}
	}
	geth(n);
}

int a[1000001];

int main()
{
	init(R);
	
	int n=1000000, i;
	for(i=1;i<=n;++i) a[i]=rand();
	
	double s=clock();

	for(i=1;i<=n;++i) insert(R, a[i]);
	
	for(i=1;i<=n;++i) find(R, a[i]);
	
	for(i=1;i<=n;++i) sterge(R, a[i]);
	printf("%lf\n",(clock()-s)/(double)CLOCKS_PER_SEC); 
	return 0;
}