#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
const int NN=2e5+100;
vector<int> vec[NN];
int bit[NN];
int seg[4*NN];
vector<int> order;
void build(int p,int s,int e)
{
if(s==e){
seg[p]=1;
return;
}
build(p*2,s,(s+e)/2);
build(p*2+1,(s+e)/2+1,e);
seg[p]=seg[p*2]+seg[p*2+1];
}
int get3(int p,int s,int e,int tar)
{
if(s==e){
return s;
}
// cout<<s<<" "<<e<<" "<<tar<<" "<<seg[p*2]<<endl;
if(seg[p*2]>=tar){
return get3(p*2,s,(s+e)/2,tar);
}
else{
return get3(p*2+1,(s+e)/2+1,e,tar-seg[p*2]);
}
}
void update(int p,int s,int e,int i)
{
if(s==e){
seg[p]=0;
return;
}
int mid=(s+e)/2;
if(i<=mid){
update(p*2,s,mid,i);
}
else{
update(p*2+1,mid+1,e,i);
}
seg[p]=seg[p*2]+seg[p*2+1];
}
void add(int idx)
{
while(idx<NN){
bit[idx]++;
idx+=(idx&-idx);
}
}
int get(int idx)
{
int ret=0;
while(idx>0){
ret+=bit[idx];
idx-=(idx&-idx);
}
return ret;
}
int get(int p,int s,int e,int a,int b)
{
if(a<=s&&e<=b)return seg[p];
if(s>b||e<a)return 0;
return get(p*2,s,(s+e)/2,a,b)+get(p*2+1,(s+e)/2+1,e,a,b);
}
int find_best(int n){
for(int i=0;i<n;i++)order.push_back(i);
shuffle(order.begin(),order.end(),rng);
int cnt=0;
int mx=0;
for(auto x:order){
cnt++;
vec[x]=ask(x);
int h=vec[x][0]+vec[x][1];
mx=max(mx,h);
if(cnt==20){
break;
}
}
// cout<<mx<<endl;
build(1,0,n-1);
while(1){
int l=0,r=n-1;
while(l<=r){
int v=0;
if(l!=0)v+=get(1,0,n-1,0,l-1);
// cout<<v<<" ";
v+=(get(1,0,n-1,l,r)+1)/2;
// cout<<get(1,0,n-1,l,r)<<" ";
// cout<<v<<"\n";
int mid=get3(1,0,n-1,v);
if(vec[mid].empty()){
vec[mid]=ask(mid);
}
int h=vec[mid][0]+vec[mid][1];
// cout<<l<<" "<<r<<" "<<mid<<" "<<vec[mid][0]<<" "<<vec[mid][1]<<" "<<v<<endl;
if(h==0)return mid;
if(h!=mx){
update(1,0,n-1,mid);
add(mid+2);
break;
}
if(vec[mid][0]-get(mid+2)){
// cout<<"l\n";
r=mid-1;
}
else{
// cout<<"r\n";
l=mid+1;
}
}
}
assert(0);
}
