#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
int mk = min((int)sqrt(n) + 5, n);
int mx = -1;
int n1, n2;
int lst = -1;
for (int i = 0; i < mk; i++) {
auto vi = ask(i);
if (vi[0] + vi[1] == 0) {
return i;
}
if (vi[0] + vi[1] >= mx) {
n1 = vi[0], n2 = vi[1];
mx = vi[0] + vi[1];
lst = i;
}
}
while (1) {
int l = lst + 1, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
auto vi = ask(mid);
if (vi[0] + vi[1] == mx) {
if (vi[0] > n1) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
r = mid;
}
}
auto vi = ask(l);
if (vi[0] + vi[1] == 0) {
return l;
}
n1++, n2--;
}
}
