#include "richest.h"
//#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define repp(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int N=1e6+100;
int n,p[N];
vector<int> A,B,res,tmp,num,chk,ans;
int mx[1005][1005];
//vector<int> ask(vector<int> a,vector<int> b){
//	int len=a.size();
//	cout<<"? "<<len<<endl;
//	vector<int> gt;
//	rep(i,0,len-1){
////		cout<<"? "<<a[i]<<" "<<b[i]<<endl;
//		gt.pb(((p[a[i]]>p[b[i]])?a[i]:b[i]));
//	} 
//	return gt;
//}
void qry(){
	res.clear();
	res=ask(A,B);
	A.clear();B.clear();
}
int get_max(int siz){
	int top=-1;
	rep(i,0,siz-1) rep(j,0,i-1) mx[i][j]=tmp[++top];
	int pos=0;
	rep(i,1,siz-1) if(mx[i][pos]==chk[i]) pos=i;
	int ret=chk[pos];
	chk.clear();tmp.clear();
	return ret; 
}
/*
0 2
0 2
0 2
0 2
1 3
1 6
-4 19
0 183
*/
void solve(int len,int opt){
	int tot=num.size(),bl=tot/len;
	if(bl==1){
		rep(i,0,tot-1) rep(j,0,i-1) A.pb(num[i]),B.pb(num[j]);
		qry();
		int top=-1;
		rep(i,0,tot-1) chk.pb(num[i]);
		rep(i,0,tot-1) rep(j,0,i-1) tmp.pb(res[++top]);
		num.clear();
		num.pb(get_max(tot));
		return;
	}
	if(opt>=0){
		int l=-1,r=-1;
		rep(i,1,bl){
			l=r+1,r=l+len-1;
			if(i==bl) r+=opt;
			rep(j,l,r) rep(k,l,j-1) A.pb(num[j]),B.pb(num[k]);
		}
		qry();
		int top=-1;
		l=r=-1;
		rep(i,1,bl){
			l=r+1,r=l+len-1;
			if(i==bl) r+=opt;
			rep(j,l,r) chk.pb(num[j]);
			rep(j,l,r) rep(k,l,j-1) tmp.pb(res[++top]);
			ans.pb(get_max(r-l+1));
		}
	}
	else{
		++bl;
		int l=-1,r=-1;
		rep(i,1,bl){
			l=r+1,r=l+len-1;
			if(i<=5) --r;
			rep(j,l,r) rep(k,l,j-1) A.pb(num[j]),B.pb(num[k]);	
		}
		qry();
		int top=-1;
		l=r=-1;
		rep(i,1,bl){
			l=r+1,r=l+len-1;
			if(i<=5) --r;
			rep(j,l,r) chk.pb(num[j]);
			rep(j,l,r) rep(k,l,j-1) tmp.pb(res[++top]);
			ans.pb(get_max(r-l+1));
		}
	}
	num=ans;
	ans.clear();
}
int richest(int nn,int t,int s){
	n=nn;
	rep(i,0,n-1) num.pb(i);
	if(n<=1000) solve(n,0);
	else{
		solve(2,0);
		solve(2,0);
		solve(2,0);
		solve(2,0);
		solve(3,1);
		solve(6,1);
		solve(19,-4);
		solve(183,0);
	}
	int ret=num[0];
	num.clear();
	return ret;
}

//int main(){
//	int m=1000000;
//	rep(j,1,10){
//		rep(i,0,m-1) p[i]=(i+j)%m;
//		cout<<richest(m,10,m*2)<<endl;
//	}
//}