#include "prize.h"
#include <bits/stdc++.h>
int find_best(int n) {
std::vector<std::vector<int>> dp(n);
auto query = [&](int i) -> std::vector<int> {
if (dp[i].size()) return dp[i];
return dp[i] = ask(i);
};
if (n <= 5000) {
for (int i = 0; i < n; i++) {
auto res = query(i);
if (res[0] + res[1] == 0) {
return i;
}
}
return 0;
}
int answer = -1;
std::vector<std::set<int>> mp(n);
auto go = [&](auto self, int l, int r) -> void {
if (l > r) return;
if (answer >= 0) return;
int m = (l + r) / 2;
auto res = query(m);
auto rnk = res[0] + res[1];
if (res[0] + res[1] == 0) {
answer = m;
return;
}
auto it = mp[rnk].insert(m).first;
if (it == mp[rnk].begin()) {
if (res[0]) self(self, l, m - 1);
} else {
auto r1 = query(*std::prev(it));
if (res[0] - r1[0] > 0) {
self(self, l, m - 1);
}
}
if (answer >= 0) return;
it = mp[rnk].find(m);
if (it == --mp[rnk].end()) {
if (res[1]) self(self, m + 1, r);
} else {
auto r2 = query(*std::next(it));
if (r2[0] - res[0] > 0) {
self(self, m + 1, r);
}
}
};
go(go, 0, n - 1);
return answer;
}
