#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];
int cq;
pii cnt(int pos){
if(use[pos])return res[pos];
use[pos]=1;
cq++;
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;
// cout<<r<<"\n";
for(int j=0;j<min(n,L);j++){
cntMx=max(cntMx,sum(j));
r++;
if(sum(j)==0)return j;
if(cntMx*cntMx+1>n){
// cout<<j<<'\n';
break;
}
}
// cout<<r<<" "<<cq<<"\n";
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();
// cout<<cq<<"\n";
if(c==0)continue;
if(c==r-l+1){
// cout<<"??\n";
for(int i=l;i<=r;i++){
if(sum(i)==0){
return i;
}
}
continue;
}
// cout<<l<<" "<<r<<" "<<c<<" "<<pl<<"\n";
int tl=(l+r)/2,tr=(l+r)/2;
// cout<<sum(tl)<<" "<<cntMx<<"\n";
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++;
}
// cerr<<tl<<" "<<tr<<"\n";
if(tl>=l){
int L=cnt(tl).F-pl;
if(l<=tl-1)q.push({{l,tl-1},{L,pl}});
}
if(tr<=r){
int R=c-cnt(tr).F+pl;
if(tr+1<=r){
q.push({{tr+1,r},{R,cnt(tr).F}});
}
}
}
return -1;
}
