#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
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 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<<mid<<" "<<u<<" "<<v<<endl;
if(!u){
ans=mid+1;
break;
}else{
if(u+v==1){
if(u){
r=mid-1;
R=mid-1;
}else{
l=mid+1;
L=mid+1;
}
}else{
if(u<=i){
l=mid+1;
}else{
r=mid-1;
}
}
}
}
assert(ans!=-1);
L=ans;
}
return 0;
}
