#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
const int C=500;
const int CC=25;
int find_best(int n){
int mx=0;
for(int i=0;i<min(C,n);i++){
vector<int>res=ask(i);
if(res[0]+res[1]==0)
return i;
mx=max(mx,res[0]+res[1]);
}
for(int i=C;i<n;i++){
vector<int>res=ask(i);
if(res[0]+res[1]==0)
return i;
if(res[0]+res[1]<mx)
continue;
if(i+C<n and ask(i+C)==res)
i+=C;
else if(i+CC<n and ask(i+CC)==res)
i+=CC;
else{
int st=i+1,en=min(n-1,i+CC);
while(st+1<en){
int mid=(st+en)>>1;
if(ask(mid)==res)
st=mid;
else
en=mid;
}
if(ask(en)==res)
i=en;
else
i=st;
}
}
return -1;
}
