#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
int cutoff = 0;
int lef = 0;
int ind = -1;
for(int i = 0; i < min(n,700); i++) {
vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
if(cutoff<res[0]+res[1]) {
cutoff=res[0]+res[1];
ind=i;
lef=res[0];
}
}
bool val[n];
fill(val,val+n,0);
while(1){
int lo = ind;
int hi = min(n-1,lo+450);
while(lo<hi){
int mid = (lo+hi+1)/2;
vector<int>res = ask(mid);
if(res[0]==lef&&res[0]+res[1]==cutoff){
lo=mid;
}
else{
hi=mid-1;
}
}
fill(val+ind,val+lo+1,1);
ind=lo;
while(++ind<n){
vector<int>res = ask(ind);
if(res[0]+res[1]==cutoff){
break;
}
if(res[0]+res[1]==0){
return ind;
}
}
if(ind==n){
break;
}
lef=ask(ind)[0];
}
for(int i = 0;i<n;i++){
if(val[i])
continue;
vector<int>res = ask(i);
if(res[0]+res[1]==0){
return i;
}
}
return -1;
}
