#include "prize.h"
#include <map>
#include <set>
#include <vector>
std::map<int, std::set<int>> trace;
std::vector<int> left;
int dfs(const int l, const int r) {
if (l > r) {
return -1;
}
const auto m = (l + r) / 2;
const auto get = ask(m);
left[m] = get[0];
const auto sum = get[0] + get[1];
if (sum == 0) {
return m;
}
auto itr = trace[sum].insert(m).first;
if (itr == trace[sum].begin() || left[*std::prev(itr)] != left[m]) {
const auto tmp = dfs(l, m - 1);
if (tmp != -1) {
return tmp;
}
}
if (itr == trace[sum].end() || left[*std::next(itr)] != left[m]) {
const auto tmp = dfs(l, m - 1);
if (tmp != -1) {
return tmp;
}
}
return -1;
}
int find_best(int n) {
left.resize(n);
return dfs(0, n - 1);
}
