#include "prize.h"
#include <vector>
#include <algorithm>
using namespace std;
int find_best(int n) {
if(n <= 3000){
for(int i=0; i<n; i++){
vector<int> resp = ask(i);
if(resp[0]+resp[1] == 0) return i;
}
}
vector<int> resp;
int m = 0;
for(int i=0; i<500; i++){
resp = ask(i);
if(resp[0]+resp[1] == 0) return i;
m = max(m, resp[0]+resp[1]);
}
int bnd=0;
for(int i=0; i<m; i++){
int l=bnd, r=n-1, res=-1;
while(l<=r){
int mid = (l+r)/2;
resp = ask(mid);
if(resp[0]+resp[1] == 0) return mid;
if(resp[0]+resp[1] != m) res = mid, r = mid-1;
else if(resp[0] == i) l = mid+1;
else r = mid-1;
}
bnd = res+1;
}
return 0;
}
