#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;
int zuletz;
for (int ind = 0; ind < 476; ind++){
vector <int> v = query(ind);
if (v[0]+v[1]==0){return ind;}
if (v[0]+v[1]>mx){
mx=v[0]+v[1];
zuletz = ind;
}
}
for (int i=0; i<zuletz; i++){vv.push_back(i);}
while(vv.size()<mx){
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;}
}
auto v=query(l);
if (v[0]+v[1]==0){return l;}
vv.push_back(l);
}
return -1;
}
