#include "prize.h"
#include <bits/stdc++.h>
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 10;
int find_best(int n) {
map<int, vector<int>> mp;
auto _ask = [&](int x) {
if (mp.count(x)) return mp[x];
auto res = ask(x);
return mp[x] = res;
};
int mx = 0;
for (int i = 0; i < min(n, N); i++) {
auto res = _ask(i);
mx = max(mx, res[0] + res[1]);
if (res[0] + res[1] == 0) return i;
}
int ANS = -1;
auto solve = [&](auto&& s, vector<int> ask, int ml, int mr) -> void {
if (ml > mr || ask.empty()) return;
int want = (ml + mr) / 2;
int tl = 0, tr = sz(ask) - 1, ans = -1;
/*
cerr << "CUR ML MR WANT " << ml << " " << mr << " " << want << '\n';
for (int x : ask) cerr << x << " ";
cerr << '\n';
*/
while (tl <= tr) {
int mid = (tl + tr) / 2;
auto res = _ask(ask[mid]);
//cerr << "ASK " << ask[mid] << " " << res[0] << " " << res[1] << endl;
if (res[0] + res[1] == 0) {
ANS = ask[mid]; return;
}
if (res[0] + res[1] < mx) {
ask.erase(ask.begin() + mid);
tr--; continue;
}
else {
if (res[0] >= want) ans = mid, tr = mid - 1;
else tl = mid + 1;
}
}
/*
cerr << "DONE " << ans << endl;
for (int x : ask) cerr << x << " ";
cerr << '\n';
*/
if (!~ans) return;
auto res = _ask(ask[ans]);
if (res[0] + res[1] == 0) {
ANS = ask[ans]; return;
}
if (ans - 2 >= 0 && !~ANS) {
s(s, vector<int>(ask.begin(), ask.begin() + ans - 1), ml, want - 1);
}
if (ans + 1 < sz(ask) && !~ANS) {
s(s, vector<int>(ask.begin() + ans + 1, ask.end()), want + 1, mr);
}
};
vector<int> idx(n);
iota(all(idx), 0);
solve(solve, idx, 1, mx);
return ANS;
}
