#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int con = 471;
int find_best(int n) {
if(n < con) {
for(int i = 0; i < n; ++i) {
vector<int> ret = ask(i);
if(ret[0] + ret[1] == 0) return i;
}
}
int mx = 0;
for(int i = 0; i < con; ++i) {
vector<int> ret = ask(i);
mx = max(mx, ret[0] + ret[1]);
if(ret[0] + ret[1] == 0) return i;
}
int ptr = con;
while(ptr < n) {
vector<int> ret = ask(ptr);
if(ret[0] + ret[1] == 0) return ptr;
if(ret[0] + ret[1] == mx) {
int l = ptr, r = n-1;
while(l < r) {
int m = (l + r + 1) >> 1;
if(ret == ask(m)) l = m;
else r = m-1;
}
ptr = l;
}
ptr++;
}
return 0;
}
