#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(nullptr));
const int N=2e5+5;
struct fenwick{
int t[N];
void add(int i,int v){
i++;
while(i<N)t[i]+=v,i+=i&-i;
}
int read(int i){
i++;
int res=0;
while(i>0)res+=t[i],i-=i&-i;
return res;
}
}f;
int cnt=0;
int n;
int ans=-1;
vector<vector<int>> mem(N);
int mx;
vector<int> ask2(int x){
if(mem[x].empty()){
assert(++cnt<=1e4);
mem[x]=ask(x);
}
return mem[x];
}
void bsearch(int l,int r){
int m=(l+r)/2;
int idx=m;
auto res=ask2(idx);
int val=res[0]+res[1];
if(val==0)ans=m;
if(l==r){
f.add(l,1);
return;
}
while(val<mx&&idx+1<=r){
f.add(idx,1);
idx++;
res=ask2(idx);
val=res[0]+res[1];
if(val==0)ans=m;
}
if(res[0]-f.read(idx-1)){
if(l<=m-1)bsearch(l,m-1);
}
if(res[1]-(f.read(N)-f.read(idx))){
if(idx+1<=r)bsearch(idx+1,r);
}
}
int find_best(int _n) {
n=_n;
for(int i=0;i*i<=n;i++){
auto res=ask2(i);
mx=max(mx,res[0]+res[1]);
}
for(int i=0;i*i<n;i++){
auto res=ask2(i);
if(res[0]+res[1]==mx)continue;
if(res[0]+res[1]==0)return i;
f.add(i,1);
}
bsearch(0,n-1);
return ans;
}
