#include<bits/stdc++.h>
using namespace std;
#include "richest.h"
bool vis[1000005];
int richest(int N, int T, int S) {
	if(N<=1000)
	{
		memset(vis,0,sizeof(vis));
		vector<int>a,b,c;
		for(int i=0;i<N;i++)
		{
			for(int j=i+1;j<N;j++)a.emplace_back(i),b.emplace_back(j);
		}
		c=ask(a,b);
		int tot=0;
		for(int i=0;i<N;i++)
		{
			for(int j=i+1;j<N;j++)
			{
				if(c[tot]==i)vis[j]=1;
				else vis[i]=1;
				tot++;
			}
		}
		for(int i=0;i<N;i++)if(!vis[i])return i;
	}
	memset(vis,0,sizeof(vis));
	int f[10];
	f[1]=500000,f[2]=250000,f[3]=125000,f[4]=62500,f[5]=20832,f[6]=3472,f[7]=183,f[8]=1;
	for(int i=1;i<=8;i++)
	{
		vector<int>v,a,b,c;
		for(int j=0;j<N;j++)if(!vis[j])v.emplace_back(j);
		int x=v.size()/f[i],y=v.size()%f[i],sum=0;
		for(int K=1;K<=f[i];K++)
		{
			int cnt=x;
			if(K<=y)cnt++;
			for(int j=0;j<cnt;j++)
			{
				for(int k=j+1;k<cnt;k++)a.emplace_back(v[sum+j]),b.emplace_back(v[sum+k]);
			}
			sum+=cnt;
		}
		c=ask(a,b);
		for(int j=0;j<c.size();j++)
		{
			if(c[j]==a[j])vis[b[j]]=1;
			else vis[a[j]]=1;
		}
	}
	for(int i=0;i<N;i++)if(!vis[i])return i;
}