#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 = 450; 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); }