#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
const int need = 473;
int find_best(int n) {
int mxcnt = 0;
vector<int> res;
int nonmax = 0;
for (int i = 0; i < min(n, need); ++i) {
res = ask(i);
if (res[0] + res[1] == 0) {
return i;
}
if (res[0] + res[1] > mxcnt) {
mxcnt = res[0] + res[1];
nonmax = i;
} else if (res[0] + res[1] < mxcnt) {
++nonmax;
}
}
int last = need - 1;
while (true) {
int left = last, right = n;
while (right - left > 1) {
int mid = left + (right - left) / 2;
res = ask(mid);
if (res[0] + res[1] == 0) {
return mid;
}
if (res[0] + res[1] < mxcnt) {
right = mid;
} else if (res[0] == nonmax) {
left = mid;
} else {
right = mid;
}
}
assert(right != n);
last = right;
}
}
