#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define sz(s) (int)s.size()
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int MAX=2e5+10;
bool use[MAX];
pii res[MAX];
pii cnt(int pos){
if(use[pos])return res[pos];
use[pos]=1;
vector<int> v=ask(pos);
return res[pos]={v[0],v[1]};
}
int sum(int pos){
pii c=cnt(pos);
return c.F+c.S;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){
return rng()%(r-l+1)+l;
}
int cntMx;
int find_best(int n){
cntMx=0;
int L=500;
int r=0;
for(int j=0;j<min(n,L);j++){
cntMx=max(cntMx,sum(j));
// r++;
if(sum(j)==0)return j;
if(cntMx>n/2)break;
}
int pref=0;
// for(int j=0;j<r;j++){
// if(sum(j)!=cntMx)pref++;
// }
queue<pair<pii,pii>> q;
q.push({{r,n-1},{cntMx,pref}});
while(!q.empty()){
int l=q.front().F.F,r=q.front().F.S,c=q.front().S.F,pl=q.front().S.S;
q.pop();
if(c==0)continue;
if(c==r-l+1){
for(int i=l;i<=r;i++){
if(sum(i)==0)return i;
}
continue;
}
int tl=(l+r)/2,tr=(l+r)/2;
while(tl>=l&&sum(tl)!=cntMx){
if(sum(tl)==0)return tl;
tl--;
}
while(tr<=r&&sum(tr)!=cntMx){
if(sum(tr)==0)return tr;
tr++;
}
int L=cnt(tl).F-pl;
int R=c-L-max(0,tr-tl-1);
// if(L+R!=c){
// cout<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
// }
if(l<=tl-1)q.push({{l,tl-1},{L,pl}});
if(tr+1<=r)q.push({{tr+1,r},{R,cnt(tr).F}});
}
return -1;
}
