#include "prize.h"
#include <vector>
#include <stack>
#include <utility>
#include <map>
std::map<int, std::map<int, std::pair<int, int> > > mp;
int find_best(int n) {
std::stack< std::pair<int, int> > st;
st.emplace(0, n - 1);
while (!st.empty()) {
int lo = st.top().first;
int hi = st.top().second;
st.pop();
int mid = (lo + hi) / 2;
std::vector<int> q = ask(mid);
int l = q[0], r = q[1];
// the same type nodes are mp[l+r], key in mp[l+r] is the possible possition
// sort mp[l+r]'s key using upper_bound to find the first position that is after mid
// if for that position p1, r[p1] == r[mid], then we know we don't need push right interval
// upper_bound -1 is the position that is before or equal to mid
// if for that position p2, l[p2] == l[mid], then we know we don't need push left interval
auto rIt = mp[l + r].upper_bound(mid);
bool processLeft = true, processRight = true;
if (!(rIt == mp[l + r].begin())) {
// check if left interval can be ignored
auto lIt = rIt; --lIt;
if (lIt->second.first == l) {
processLeft = false;
}
}
if ((!(rIt == mp[l + r].end()) && rIt->second.second == r)||(r == 0)) {
processRight = false;
}
mp[l + r][mid] = {l, r};
if (l == 0 && r == 0) return mid;
if (l == 0) st = std::stack< std::pair<int, int> >();
if (lo != mid && processLeft) st.emplace(lo, mid - 1);
if (hi != mid && processRight) st.emplace(mid + 1, hi);
}
return 0;
}
