#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> cache;
vector<int> ask(int i);
vector<int> ask_(int i){
assert(0 <= i && i <cache.size());
if(cache[i][0] != -1) return cache[i];
cache[i] = ask(i);
if(cache[i][0] == 0 && cache[i][1] == 0) return {};
return cache[i];
}
int find_best(int n) {
cache.resize(n, {-1, -1});
const int SQRT = 500;
int mx_sm = 0; // per capire se è il peggiore
int l2_ = 0;
for(int i = 0; i<min(SQRT, n); i++){
if(ask_(i).empty()) return i;
if(mx_sm < cache[i][0]+cache[i][1]){
l2_ = cache[i][0];
mx_sm = cache[i][0]+cache[i][1];
}
else if(mx_sm > cache[i][0]+cache[i][1]) l2_++;
}
auto rec = [&](int l, int r, int _l, int _r, auto&& rec)->int{
if(l>r || _l>_r) return -1;
int m = (l+r)/2;
int m0 = (l+r)/2;
for(; m <= r; m++){
if(ask_(m).empty()) return m;
if(cache[m][0] + cache[m][1] == mx_sm){
int t = rec(l, m0-1, _l, cache[m][0]-(m-m0)-1, rec); //
if(t != -1) return t;
t = rec(m+1, r, cache[m][0], _r, rec);
if(t != -1) return t;
return -1;
}
}
return rec(l, m0-1, _l, _r-(m-m0), rec); //
};
return rec(SQRT, n-1, l2_, mx_sm-1, rec);
}
