#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_best2(int n, vector<int> &idx) {
// cache.resize(n, {-1, -1});
const int SQRT = 30;
int mx_sm = 0; // per capire se è il peggiore
int l2_ = 0;
for(int i = 0; i<min(SQRT, n); i++){
if(ask_(idx[i]).empty()) return idx[i];
if(mx_sm < cache[idx[i]][0]+cache[idx[i]][1]){
l2_ = cache[idx[i]][0];
mx_sm = cache[idx[i]][0]+cache[idx[i]][1];
}
else if(mx_sm > cache[idx[i]][0]+cache[idx[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_(idx[m]).empty()) return idx[m];
if(cache[idx[m]][0] + cache[idx[m]][1] == mx_sm){
int t = rec(l, m0-1, _l, cache[idx[m]][0]-(m-m0)-1, rec); //
if(t != -1) return t;
t = rec(m+1, r, cache[idx[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);
}
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_++;
}
vector<int> idx;
for(int i = 0; i<min(SQRT, n); i++){
if(mx_sm > cache[i][0]+cache[i][1]) idx.push_back(i);
}
auto rec = [&](int l, int r, int _l, int _r, auto&& rec)->int{
if(l>r || _l>_r) return -1;
if(r-l == _r-_l){
for(int i = l; i<=r; i++) idx.push_back(i);
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;
}
else idx.push_back(m);
}
return rec(l, m0-1, _l, _r-(m-m0), rec); //
};
int t = rec(SQRT, n-1, l2_, mx_sm-1, rec);
if(t != -1) return t;
sort(idx.begin(), idx.end());
return find_best2(idx.size(), idx);
assert(0);
}
