#include "prize.h"
#include<vector>
using namespace std;
int ans[200000][2];
int maximo;
void q(int x){
if(ans[x][0]!=-1){
return;
}
vector<int> v=ask(x);
ans[x][0]=v[0];
ans[x][1]=v[1];
}
bool L(int i){
q(i);
if(ans[i][0]+ans[i][1]==maximo)return true;
return false;
}
int find_best(int n) {
for(int i = 0; i < n; i++) {
ans[i][0]=-1;
ans[i][1]=-1;
}
maximo=0;
int d=500;
for(int i=0;i<d;i++){
q(i);
if(ans[i][0]+ans[i][1]>maximo)maximo=ans[i][0]+ans[i][1];
if(ans[i][0]+ans[i][1]==0)return i;
}
int pointer=d;
while(pointer<n){
q(pointer);
if(ans[pointer][0]+ans[pointer][1]==0)return pointer;
if(ans[pointer][0]+ans[pointer][1]==maximo){
int lo=pointer;
int hi=n;
while(hi-lo>1){
int mid=(lo+hi)/2;
if(L(mid)){
if(ans[mid][0]==ans[pointer][0]){
lo=mid;
}else hi=mid;
}else{
hi=mid;
}
}
pointer=lo;
}
pointer++;
}
return 0;
}
