#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> speichern;
vector<int> ask(int i);
vector<int> query(int i){
if (speichern[i].size()){
return speichern[i];
}
else{
speichern[i]=ask(i);
return speichern[i];
}
}
vector <int> pos;
int find_best(int n){
//let us denote the number of item of u as f(u)
//from simple algebra we know that f(v-1)<500
//and since 17<log2(200000)<18 we know we need 18 operation
//for each query -- hence we can find every item of value
//higher than v at 18*500 = 9000 queries
int mx = 0;
speichern.resize(n);
vector <int> vv;
for (int ind = 0; ind < 500; ind++){
vector <int> v = query(ind);
if (v[0]+v[1]==0){return ind;}
mx=max(mx,v[0]+v[1]);
}
while(true){
int l=0;
int r=n-1;
if(!vv.empty()){l=vv.back()+1;}
while(l<r){
int m=(l+r)/2;
auto v=query(m);
if (v[0]+v[1]==0){return m;}
if(v[0]+v[1]<mx||v[0]>vv.size()){r=m;}
else{l=m+1;}
}
vv.push_back(l);
}
return -1;
}
