#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++){
auto [u,v]=get(rand(0,n-i));
mx=max(mx,u+v);
}
int L=0,R=n-1;
for(int i=0; i<=10000; i++){
cerr<<i<<endl;
int l=L,r=R,ans=-1;
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){
if(u){
r=mid-1;
R=min(R,mid-1);
}else{
l=mid+1;
L=max(L,mid+1);
}
}else if(u+v!=mx){
r=mid-1;
}else{
if(u<=i) l=mid+1;
else r=mid-1;
}
}
}
//assert(ans!=-1);
L=max(L,ans);
}
return 0;
}
