//#include "public_a/cpp/prize.h"
#include "prize.h"
#include <bits/stdc++.h>
int find_best(int n) {
std::vector <std::vector <int>> dp(n);
dp[0] = ask(0);
int mx = dp[0][0] + dp[0][1];
for (int last = -1, i = 0; ; i++) {
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (mid <= last) {
l = mid + 1;
continue;
}
if (dp[mid].empty()) {
dp[mid] = ask(mid);
}
if (!(dp[mid][0] + dp[mid][1])) {
return mid;
}
if (dp[mid][0] + dp[mid][1] > mx) {
mx = dp[mid][0] + dp[mid][1];
l = 0, r = n - 1;
continue;
}
if (mid <= last || (dp[mid][0] + dp[mid][1] == mx && dp[mid][0] < i)) {
l = mid + 1;
} else {
r = mid;
}
}
if (dp[last = l].empty()) {
dp[l] = ask(l);
}
if (!(dp[l][0] + dp[l][1])) {
return l;
}
}
assert(false);
return 0;
}
