#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
const int N=1000009;
int n,p[N],deg[N],m,q[N];
vector<int> a,b,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=1;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;
}
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];
}