#include "prize.h"
// #include <iostream>
#include <map>
using namespace std;
map<int, map<int, pair<int, int>>> resmap;
void resmap_push(int i, int lc, int rc) {
resmap[lc + rc][i] = {lc, rc};
}
int gogo(int fr, int to) {
// cout << "go " << fr << ' ' << to << endl;
for (auto &rsmp : resmap) {
auto &mp = rsmp.second;
auto lb = mp.lower_bound(fr);
auto ub = mp.upper_bound(to);
pair<int, int> lres, rres;
// cout << "check " << rsmp.first << endl;
if (lb == mp.begin()) {
// cout << "no lb" << endl;
lres = {0, rsmp.first};
} else {
lb--;
// cout << "lb " << lb->first << endl;
lres = lb->second;
}
if (ub == mp.end()) {
// cout << "no ub" << endl;
rres = {rsmp.first, 0};
} else {
// cout << "ub " << ub->first << endl;
rres = ub->second;
}
if (lres.first == rres.first) {
// cout << "skip" << endl;
return -1;
}
}
if (to <= fr) {
return -1;
}
int mid = (fr + to) / 2;
vector<int> res = ask(mid);
resmap_push(mid, res[0], res[1]);
if (res[0] + res[1] == 0) {
return mid;
} else {
int lrt = gogo(fr, mid);
if (lrt == -1) {
return gogo(mid + 1, to);
} else {
return lrt;
}
}
}
int find_best(int n) {
resmap.clear();
return gogo(0, n);
}
