#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h[200005];
int f=-1,N;
vector<int> query(int idx){
if(!h[idx].empty())return h[idx];
return h[idx]=ask(idx);
}
int close_left(int l,int r){
while(l<=r){
vector<int> M=query(l);
if((M[0]+M[1])==N)return l;
else if(!(M[0]+M[1])){f=l;return -1;}
l++;
}
return -1;
}
int close_right(int l,int r){
while(r>=l){
vector<int> M=query(r);
if((M[0]+M[1])==N)return r;
else if(!(M[0]+M[1])){f=r;return -1;}
r--;
}
return -1;
}
void gimme(int l,int r){
if(f!=-1)return;
if(l==r)return ;
vector<int> G=query(l),G2=query(r);
if(G2[0]==G[0])return;
int med=(l+r)>>1,k;
vector<int> M=query(med);
if(!(M[0]+M[1])){f=med;return;}
else if((M[0]+M[1])==N){
gimme(l,med);
if(f!=-1)return;
k=close_left(med+1,r);
if(f!=-1)return;
if(k!=-1)gimme(k,r);
}
else{
k=close_right(l,med-1);
if(f!=-1)return;
if(k!=-1)gimme(l,k);
if(f!=-1)return;
k=close_left(med+1,r);
if(f!=-1)return;
if(k!=-1)gimme(k,r);
}
}
int find_best(int n) {
srand(time(0));
N=0;
for (int i = 0; i < min(600,n); ++i)
{
vector<int> Y=query(i);
if(!(Y[0]+Y[1]))return i;
else N=max(N,Y[0]+Y[1]);
}
int l=close_left(0,n-1);
if(f!=-1)return f;
assert(l!=-1);
int r=close_right(l,n-1);
if(f!=-1)return f;
assert(r!=-1);
gimme(l,r);
assert(f!=-1);
return f;
}
