#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int lol = 0;
int ans = 0;
bool dude(int l, int r, int brl, int brr, int br) {
if(br == 0 || l > r) {
return false;
}
if(l == r) {
vector<int> wut = ask(l);
if(wut[0]+wut[1] == 0) {
ans = l;
return true;
}
return false;
}
vector<int> wut(0);
int midl = (l+r)/2+1;
int midr = midl-1;
int p;
for(int i = 0; i < r-l+1; i++) {
if(i%2 == 0) {
midl--;
wut = ask(midl);
p = midl;
}
else {
midr++;
wut = ask(midr);
p = midr;
}
if(wut[0]+wut[1] == 0) {
ans = p;
return true;
}
if(wut[0]+wut[1] == lol) {
if(i%2 == 0) {
if(dude(l,midl-1,brl,brr+i,wut[0]-brl)) {
return true;
}
if(dude(midr+1,r,brl+i,brr,wut[1]-brr-i)) {
return true;
}
}
else {
if(dude(l,midl-1,brl,brr+i,wut[0]-i-brl)) {
return true;
}
if(dude(midr+1,r,brl+i,brr,wut[1])) {
return true;
}
}
break;
}
}
return false;
}
int find_best(int n) {
for(int i = 0; i <= min(n-1,max((int)floor(sqrt(n)),lol)); i++) {
vector<int> wut = ask(i);
lol = max(lol,wut[0]+wut[1]);
}
dude(0,n-1,0,0,lol);
return ans;
}
