#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
vector<int> isi[maxn+2];
vector<int>query(int idx){
if(isi[idx][0]!=-1)return isi[idx];
isi[idx]=ask(idx);
return isi[idx];
}
int sum(int idx){
if(isi[idx][0]==-1)isi[idx]=ask(idx);
return isi[idx][0]+isi[idx][1];
}
map<int,pair<int,int> >mp[maxn+2];
int dnc(int l,int r){
if(l>r)return -1;
int mid=(l+r)/2; query(mid);
if(sum(mid)==0)return mid;
bool lf=true,rg=true;
auto it=mp[sum(mid)].lower_bound(mid);
if(it!=mp[sum(mid)].end()){
if((*it).second.first-isi[mid][0]==0)rg=false;
}
if(it!=mp[sum(mid)].begin()){
it--;
if((*it).second.first-isi[mid][0]==0)lf=false;
}
int ans=-1;
mp[sum(mid)][mid]={isi[mid][0],isi[mid][1]};
if(rg)ans=max(ans,dnc(mid+1,r));
if(lf)ans=max(ans,dnc(l,mid-1));
return ans;
}
int find_best(int n) {
for(int q=0;q<n;q++)isi[q]={-1,-1};
return dnc(0,n-1);
}
