#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#define oo 0x3f3f3f3f
#define N 1000001

using namespace std;

struct nod
{
	int v;
	int p;
	int nr;
	nod  *l, *r;
	nod(){v=p=-oo; l=r=0;nr=0;}
};
typedef nod* tree;

tree nil;

void init()
{
	srand(time(0));
	nil=new nod;
}

inline void getnr(tree &n)
{
	if(n == nil) return;
	
	n->nr=1 + n->l->nr + n->r->nr;
}


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

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

inline void insert(tree &n, int v)
{
	if(n == nil)
	{
		n=new nod;
		n->v=v;
		n->p=rand();
		n->l=n->r=nil;
		n->nr=1;
		return;
	}
	
	if(v < n->v) 
	{
		insert(n->l, v);
		//if(n->l->p > n->p)rotleft(n);
	}
	
	if(v > n->v)
	{
		insert(n->r, v);
		//if(n->r->p > n->p) rotright(n);
	}
	
	getnr(n);
}


tree aib[N];
int n;

inline void update(int x, int v)
{
	for(int i=x; i <= n; i += i & -i)
	{
		if(aib[i] == 0) aib[i]=nil;
		insert(aib[i], v);
	}
}

inline int query(int x)
{
	int nr=0;
	for(int i=x; i ; i -= i & -i)
		++nr;
	
	return nr;
}


vector<tree> Q1, Q2;

inline void que(int x, vector<tree> &Q)
{
	Q.clear();
	for(int i=x; i ; i -= i & -i)
		Q.push_back(aib[i]);
}


inline void count(tree n, int v, int &sum)
//cate elemente sunt mai mici decat v
{
	if(n == nil) return;
	if(v == n->v) 
	{
		sum += n->l->nr+1;
		return;
	}
	
	if(v < n->v) count(n->l, v, sum);
	if(v > n->v) 
	{
		sum += n->l->nr + 1;
		count(n->r, v, sum);
	}
	
}



int main()
{
	n=50000;
	
	init();
	

	
	
	
	double s=clock();
	
	
	int i;
	for(i=1; i <= n; ++i) update(i, rand());
	

	
	srand(66521);
	int p,k, q,j;
	int cnt, ii,s1,s2;
	for(i=1; i <= n; ++i)
	{
			
		p=(rand()*rand())%n+1;
		q=(rand()*rand())%n+1;
		k=(rand()*rand())%n+1;

		if(p > q) p^=q^=p^=q;
		que(q, Q1);
		que(p, Q2);
		
		
		for(ii=1, cnt=(1<<20); cnt; cnt>>=1)
		{
			
			s1=0;
			s2=0;
			for(j=0; j < Q1.size(); ++j)
				count(Q1[j], ii+cnt, s1);
			
			for(j=0; j < Q2.size(); ++j)
				count(Q2[j], ii+cnt, s2);
			
			
			if(s1 - s2 >= k) ii += cnt; 
		}
		

	}
	
//	printf("%d %d\n", Q1.size(), Q2.size());
	
	
	
	
	
	printf("%lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
	
	return 0;
}