#include "prize.h"
#include "iostream"
using namespace std;
int find_best(int n) {
int mx = 0;
for (int i = 0; i < min(n, 500); i ++) {
auto pr = ask(i);
mx = max(mx, pr[0] + pr[1]);
if (0 == pr[0] + pr[1]) return i;
}
int ls = 500;
for (; ls < n; ls ++) {
int ps = -1;
for (; ls < n; ls ++) {
auto pr = ask(ls);
int sm = pr[0] + pr[1];
if (0 == sm) return ls;
if (sm == mx) {
ps = pr[1];
break;
}
}
int rs = n;
while (1 < rs - ls) {
int mi = (ls + rs) / 2;
auto pr = ask(mi);
int sm = pr[0] + pr[1];
if (0 == sm) return mi;
if (sm != mx) rs = mi;
if (0 == ps - pr[1]) ls = mi;
else rs = mi;
}
}
return 0;
}
