#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int mx=0, ans=-1;
vector<pii> ooga;
pii query(int a){
if (ooga[a].fi!=-1)return ooga[a];
vector<int> res=ask(a);
if (!(res[0]+res[1]))ans=a;
return ooga[a]=mp(res[0], res[1]);
}
void dnc(int l, int r, int cl, int cr){
if (l>r)return;
for (int i=0; i<=r-l; ++i){
int lm=(l+r)/2-i/2, rm=(l+r)/2+(i+1)/2, m=(i%2?rm:lm);
pii res=query(m);
if (ans!=-1)return;
if (res.fi+res.se==mx){
if (i%2){
if (res.se>cr)dnc(rm+1, r, res.fi, cr);
if (res.fi-rm+lm>cl)dnc(l, lm-1, cl, res.se+rm-lm);
}
else{
if (res.fi>cl)dnc(l, lm-1, cl, res.se);
if (res.se-rm+lm>cr)dnc(rm+1, r, res.fi+rm-lm, cr);
}
return;
}
}
}
int find_best(int n){
if (n==1)return 0;
ooga.resize(n, mp(-1, -1));
int id=0;
for (int i=0; i<sqrt(n)+30&&mx<27; ++i){
pii res=query(i);
if (ans!=-1)break;
if (res.fi+res.se>mx)mx=res.fi+res.se, id=i;
}
dnc(id, n-1, id, 0);
return ans;
}
