#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
const int N=1000009;
int w[N],n,p[N],deg[N],m,q[N],sum;
vector<int> a,b,c;
//vector<int> ask(vector<int> a,vector<int> b){
//	vector<int> c;
//	for(int i=0;i<a.size();i++)
//	    if(w[a[i]]>w[b[i]])c.push_back(a[i]);
//	    else c.push_back(b[i]);
//	return c;
//}
void solve(int x){
	a.clear();
	b.clear();
	int t=n/x;
	int l=0,r=0;
	for(int i=1;i<=x-n%x;i++){
		l=r+1;
		r=l+t-1;
		for(int j=l;j<=r-1;j++)
		    for(int k=j+1;k<=r;k++){
		    	a.push_back(p[j]);
		    	b.push_back(p[k]);
			}
	}
	for(int i=1;i<=n%x;i++){
		l=r+1;
		r=l+t;
		for(int j=l;j<=r-1;j++)
		    for(int k=j+1;k<=r;k++){
		    	a.push_back(p[j]);
		    	b.push_back(p[k]);
			}
	}
	c=ask(a,b);
	int tmp=0;
	for(int i=0;i<=1000000;i++)
	    deg[i]=0;
	for(int i=0;i<c.size();i++){
		if(a[i]==c[i])deg[b[i]]++;
		else deg[a[i]]++;
	}
	m=0;
	for(int i=1;i<=n;i++){
		if(deg[p[i]]!=0)continue;
		q[++m]=p[i];
	}
	n=m;
	for(int i=1;i<=n;i++)
	    p[i]=q[i];
	sum+=c.size();
}
int richest(int N,int T,int S){
	n=N;
	for(int i=1;i<=n;i++)
	    p[i]=i-1;
	if(n==1000)
		solve(1);
	else{
		solve(500000);
		solve(250000);
		solve(125000);
		solve(62496);
		solve(20832);
		solve(3472);
		solve(183);
		solve(1);
	}
	return p[1];
}
//int main(){
//	n=1000000;
//	mt19937 rnd(time(0));
//	for(int i=1;i<=n;i++)
//	    w[i-1]=rnd()/4;
//	printf("%d ",richest(n,10000000,10000000));
//	int fnd=0;
//	for(int i=1;i<=1000000-1;i++)
//	    if(w[i]>w[fnd])fnd=i;
//	printf("%d %d",fnd,sum);
//	return 0;
//}