#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
int MAXQ = 0;
vi nextrow,cur;
vi currow;
void dnc(int s, int e, int loff, int roff){
if (s > e)return;
// cout<<"DNC "<<s<<' '<<e<<' '<<loff<<' '<<roff<<'\n';
if (loff + roff == MAXQ)return; // None exist in this range
if (s == e){
nextrow.pb(currow[s]);
return;
}
int m = (s+e)/2;
int done=0;
while(m<=e){
cur = ask(currow[m]);
// cout<<"Query "<<m<<' '<<cur[0]<<' '<<cur[1]<<'\n';
if (cur[0]+cur[1] == MAXQ)break;
nextrow.pb(currow[m]);
++done;
++m;
}
pi x = mp(cur[0],cur[1]);
int lm = (s+e)/2;
dnc(s,lm-1,loff,x.s+done);
dnc(m+1,e,x.f,roff);
}
int find_best(int n) {
for (int i=0;i<n;++i)currow.pb(i);
while(1){
MAXQ = 0;
for (int i=0;i<sqrt(SZ(currow))+5&&i<SZ(currow);++i){
vi x = ask(currow[i]);
MAXQ = max(MAXQ, x[0] + x[1]);
}
// cout<<MAXQ<<'\n';
dnc(0,SZ(currow)-1,0,0);
// for (auto i : nextrow)cout<<i<<' ';cout<<'\n';
// if (SZ(nextrow) == 2)break;
sort(ALL(nextrow));
if(SZ(nextrow) == 1)return nextrow[0];
swap(nextrow,currow);
nextrow.clear();
}
return 0;
}
