#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
assert(l<=r);
return uniform_int_distribution<int> (l,r)(rng);
}
pair <int,int> mp[200005];
pair <int,int> get(int i){
if(mp[i].first || mp[i].second) return mp[i];
auto vi=ask(i);
pair <int,int> ans={vi[0],vi[1]};
return mp[i]=ans;
}
int find_best(int n) {
int mx=0;
for(int i=1; i<=20; i++){
int k=rand(0,n-1);
if(i==1) k=1;
auto [u,v]=get(k);
if(!u and !v) return k;
mx=max(mx,u+v);
}
int L=0,R=n-1,kep=0;
for(int _=0; _<=1000; _++){
while(1){
auto [u,v]=get(L);
if(!u and !v) return L;
if(u+v==mx){
kep=u;
break;
}else L++;
}
int l=L,r=R,ans=-1;
// cerr<<_<<" "<<kep<<endl;
// cerr<<"range : "<<L<<" "<<R<<endl;
while(l<=r){
int mid=(l+r)>>1;
auto [u,v]=get(mid);
if(!u and !v) return mid;
// cerr<<"db : "<<l<<" "<<r<<endl;
// cerr<<mid<<" "<<u<<" "<<v<<endl;
if(!u){
ans=max(ans,mid+1);
if(u+v==mx) l=mid+1;
else break;
}else{
if(u+v==1){
r=mid-1;
R=min(R,mid-1);
}else if(u+v!=mx){
if(r-l<=100) ans=max(ans,mid+1);
r=mid-1;
}else{
if(u<=kep) l=mid+1;
else r=mid-(u-kep);
}
}
}
L=max(L+1,ans);
}
assert(0);
return 0;
}
