#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())h[idx]=ask(idx);
if(!(h[idx][0]+h[idx][1]))f=idx;
return h[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;}
else if(!M[1])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;}
else if(!M[0])return -1;
r--;
}
return -1;
}
void gimme(int l,int r){
if(l>=r)return ;
if(f!=-1)return;
vector<int> G=query(l),G2=query(r);
if(f!=-1)return;
if((G[0]+G[1])==(G2[0]+G2[1]) && (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=med+1;
if(f!=-1)return;
if(k!=-1)gimme(k,r);
}
else{
k=med;
if(f!=-1)return;
if(k!=-1)gimme(l,k);
if(f!=-1)return;
k=med+1;
if(f!=-1)return;
if(k!=-1)gimme(k,r);
}
}
int find_best(int n) {
N=0;
for (int i = 0; i < min(500,n); ++i)
{
vector<int> Y=query(i);
if(!(Y[0]+Y[1]))return i;
else N=max(N,Y[0]+Y[1]);
}
int l=min(500,n-1);
if(f!=-1)return f;
assert(l!=-1);
int r=n-1;
if(f!=-1)return f;
assert(r!=-1);
gimme(l,r);
assert(f!=-1);
return f;
}
