#include <bits/stdc++.h>
#include "prize.h"
#define ar array
using namespace std;
map<int, set<int>> where;
map<int, ar<int, 2>> mem;
map<int, map<int, int>> rightmost;
map<int, map<int, int>> leftmost;
ar<int, 2> qry(int i) {
auto it = mem.find(i);
if (it != mem.end()) return it->second;
auto v = ask(i);
int l = v[0], r = v[1];
where[l+r].insert(i);
if (!rightmost[l+r].count(l)) rightmost[l+r][l] = i;
else rightmost[l+r][l] = max(rightmost[l+r][l], i);
if (!leftmost[l+r].count(l)) leftmost[l+r][l] = i;
else leftmost[l+r][l] = min(leftmost[l+r][l], i);
return mem.insert({i, {l, r}}).first->second;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int find_best(int n) {
vector<int> idxs(n);
iota(idxs.begin(), idxs.end(), 0);
shuffle(idxs.begin(), idxs.end(), rng);
for (int rep = 0; rep < min((int)sqrt(n), n); ++rep)
qry(idxs[rep]);
/*
for (auto &&[s, idxs] : where) {
cerr << s << ": ";
for (int i : idxs)
cerr << i << ' ';
cerr << '\n';
} // */
int worst = where.rbegin()->first;
vector<ar<int, 2>> bad_ranges;
auto is_bad = [&](int i) {
auto [l, r] = qry(i);
return l+r == worst;
};
int i = 0;
while (true) {
while (i < n && !is_bad(i)) ++i;
if (i == n) break;
auto p = qry(i);
auto [l, r] = p;
auto rmit = rightmost[l+r].find(l);
auto lmit = leftmost[l+r].upper_bound(l);
int lo = rmit->second, hi;
if (lmit == leftmost[l+r].end()) hi = n-1;
else hi = lmit->second;
//cerr << lo << ' ' << hi << '\n';
while (lo != hi) {
int ce = lo + (hi-lo+1)/2;
if (qry(ce) == p) lo = ce;
else hi = ce-1;
}
bad_ranges.push_back({i, lo});
i = lo+1;
}
return *where[0].begin();
}
