// http://ioi2017.org/tasks/editorial/prize.pdf
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
vector<vector<int>> memo(n);
auto Ask = [&](int i) {
if (!memo[i].size()) {
memo[i] = ask(i);
}
};
vector<set<int>> st(n + 1);
int res = -1;
function<void(int, int)> dc = [&](int l, int r) {
if (l > r || ~res) {
return;
}
int md = (l + r) / 2;
Ask(md);
int key = memo[md][0] + memo[md][1];
if (!key) {
res = md;
return;
}
auto it = st[key].insert(md).first;
if (it == st[key].begin() ? memo[md][0] : memo[md][0] - memo[*prev(it)][0] > 0) {
dc(l, md - 1);
}
if (~res) {
return;
}
if (next(it) == st[key].end() ? memo[md][1] : memo[*next(it)][0] - memo[md][0] > 0) {
dc(md + 1, r);
}
};
dc(0, n - 1);
return res;
}
