#include <bits/stdc++.h>
using namespace std;
#include "prize.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
#define ll long long
map<int,vector<int>> mp;
int ans,cntbst;
vector<int> pre;
vector<int> query(int i){
if(mp.find(i)==mp.end()){
mp[i]=ask(i);
}
return mp[i];
}
bool dnc(int l,int r,int cnt,int le,int ri){
if(l>r||!cnt){
return false;
}
int temp=pre[r];
if(l){
temp-=pre[l-1];
}
if(temp==cnt){
return false;
}
cnt-=temp;
if(l==r){
vector<int> v=query(l);
if(!v[0]&&!v[1]){
ans=l;
return true;
}
return false;
}
int mid=((l+r)>>1);
int idx=mid;
int l1=l,r1=mid-1,l2=mid+1,r2=r;
vector<int> v=query(idx);
if(!v[0]&&!v[1]){
ans=idx;
return true;
}
else if(v[0]+v[1]==cntbst){
if(dnc(l1,r1,v[0]-le-(idx-r1-1),le,v[1]+(idx-r1-1))){
return true;
}
if(dnc(l2,r2,v[1]-ri-(l2-idx-1),v[0]+(l2-idx-1),ri)){
return true;
}
return false;
}
else{
if((idx==0&&!pre[idx])||(idx>0&&pre[idx]==pre[idx-1])){
cnt--;
}
}
while(cnt>0){
if(r1-l1+1>r2-l2+1){
idx=r1;
r1--;
}
else{
idx=l2;
l2++;
}
vector<int> v=query(idx);
if(!v[0]&&!v[1]){
ans=idx;
return true;
}
else if(v[0]+v[1]==cntbst){
if(dnc(l1,r1,v[0]-le-(idx-r1-1),le,v[1]+(idx-r1-1))){
return true;
}
if(dnc(l2,r2,v[1]-ri-(l2-idx-1),v[0]+(l2-idx-1),ri)){
return true;
}
return false;
}
else{
if((idx==0&&!pre[idx])||(idx>0&&pre[idx]==pre[idx-1])){
cnt--;
}
}
}
return false;
}
mt19937 rng(6736);
int GetRand(int l,int r){
return (rng()%(r-l+1)+l);
}
int find_best(int n){
mp.clear();
ans=-1,cntbst=0;
int thres=447;
#ifdef LOCAL
cin >> thres;
#endif
vector<int> p(n);
for(int i=0;i<n;i++){
p[i]=i;
}
pre.assign(n,0);
shuffle(p.begin(),p.end(),rng);
for(int i=0;i<min(n,thres);i++){
vector<int> v=query(p[i]);
if(!v[0]&&!v[1]){
return p[i];
}
cntbst=max(cntbst,v[0]+v[1]);
}
vector<pair<int,vector<int>>> candi;
for(int i=0;i<min(n,thres);i++){
vector<int> v=query(p[i]);
if(v[0]+v[1]!=cntbst){
pre[p[i]]=1;
}
else{
candi.push_back({p[i],v});
}
}
candi.push_back({-1,{0,cntbst}});
candi.push_back({n,{cntbst,0}});
sort(candi.begin(),candi.end());
for(int i=1;i<n;i++){
pre[i]+=pre[i-1];
}
for(int i=0;i+1<candi.size();i++){
int l=candi[i].first,r=candi[i+1].first,le=candi[i].second[0],ri=candi[i+1].second[1];
//cout << l << ' ' << r << ' ' << le << ' ' << ri << endl;
if(dnc(l+1,r-1,cntbst-le-ri,le,ri)){
return ans;
}
}
assert(false);
return -1;
}
