#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
int ix[1000005],nw[1000005],cl,cr;
vector<int> qla,qlb,an;bool v[10005];

int richest(int N, int T, int S) {
	for(int i=1;i<=10000;i++)v[i]=0;
	cl=N;for(int i=1;i<=N;i++)ix[i]=i-1;
	for(int i=1;i<=8;i++){
		if(cl==1)return ix[cl];
		qla.clear();qlb.clear();
		for(int j=1;j<cl;j++)
			qla.push_back(ix[j]),qlb.push_back(ix[j+1]);
		an=ask(qla,qlb);cr=0;
		for(int j=1;j<=cl;j++){
			if(j==1&&an[0]==ix[1]||j==cl&&an[cl-2]==ix[cl])nw[++cr]=ix[j];
			if(1<j&&j<cl&&an[j-2]==ix[j]&&an[j-1]==ix[j])nw[++cr]=ix[j];
		}for(int j=1;j<=cr;j++)ix[j]=nw[j];cl=cr;
		//for(int j=1;j<=cl;j++)cout<<ix[j]<<" ";cout<<"\n";
	}if(cl==1)return ix[cl];
	qla.clear();qlb.clear();
	for(int i=1;i<=cl;i++)
		for(int j=i+1;j<=cl;j++)
			qla.push_back(ix[i]),qlb.push_back(ix[j]);
	an=ask(qla,qlb);cr=0;
	for(int i=1;i<=cl;i++)
		for(int j=i+1;j<=cl;j++)
			v[i+j-an[cr++]]=1;
	for(int i=0;i<cl;i++)if(!v[i])return ix[i];
}