#include "prize.h"
using namespace std;
vector<int> cache[200005];
vector<int> myask(int x){
if(cache[x].empty())cache[x]=ask(x);
return cache[x];
}
int find_best(int n) {
int Max=0;
for(int i = 0;i<n&&i<500;i++){
vector<int> v=ask(i);
if(v[0]+v[1]==0)return i;
Max=max(Max,v[0]+v[1]);
}
int l=0,r=n-1;
while(true){
int Max=r,Min=l;
while(Max>Min){
int mid=(Max+Min)/2;
vector<int> v=myask(mid);
if(v[0]+v[1]==0)return mid;
if(v[0]+v[1]!=Max){
Max=mid;
}
else{
if(v[0])Max=mid-1;
else Min=mid+1;
}
}
l=Min+1;
}
/*
int Max=n-1,Min=0;
while(Max>Min){
int mid=(Max+Min)/2;
vector<int> v=ask(mid);
if(v[0]+v[1]==0){
return mid;
}
if(v[0]<v[1]){
Min=mid+1;
}
else{
Max=mid-1;
}
}
return Min;*/
}
