#include "prize.h"
#include <bits/stdc++.h>
#define lint long long
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
int res = -1;
struct state{
int i; int toLeft; int toRight;
int sum(){
return toLeft+toRight;
}
};
void get(state l, state r){
if(r.i-l.i<2){return;}
if(r.toRight==l.toRight){return;}
if(res>=0){return;}
if(r.toRight-l.toRight==r.i-l.i-1)
{
for(int i = l.i+1; i < r.i; i++){
vector<int>ans=ask(i);
if(ans[0]+ans[1]==0) res = i;
}
} else
{
int mid = (l.i+r.i)/2;
vector<int>tmp=ask(mid);
state ansl = state({mid, tmp[0], tmp[1]});
state ansr = ansl;
while(ansl.sum()<l.sum()){
if(ansl.sum()==0){res=ansl.i; return;}
tmp=ask(ansl.i-1);
ansl = state({ansl.i-1, tmp[0], tmp[1]});
}
while(ansr.sum()<l.sum()){
if(ansr.sum()==0){res=ansr.i; return;}
tmp=ask(ansr.i+1);
ansr = state({ansr.i+1, tmp[0], tmp[1]});
}
get(l, ansl);
get(ansr, r);
}
}
state getState(int i){
vector<int>tmp=ask(i);
return state({i, tmp[0], tmp[1]});
}
int find_best(int n)
{
if(n<5000&&false){
rep(i, n){
vector<int>ans=ask(i);
if(ans[0]+ans[1]==0){return i;}
}
}
state l = getState(0);
state r = getState(n-1);
int maxx=0;
rep(i, 20){
state s = getState(rand()%n);
maxx=max(maxx, s.sum());
}
while(l.sum()<maxx){
if(l.sum()==0){return l.i;}
l=getState(l.i+1);
}
while(r.sum()<maxx){
if(r.sum()==0){return r.i;}
r=getState(r.i-1);
}
get(l,r);
return res;
}
