#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand_int(int l,int r){
return l+(int)(rng()%(r-l+1));
}
const int B = 500;
const int maxn = 2e5+5;
vector<int> res[maxn];
vector<int> get(int x){
if(!res[x].empty()) return res[x];
res[x]=ask(x);res[x][1]+=res[x][0];
return res[x];
}
int N,bit[maxn],Max;
void update(int x){
for(int i=x+1;i<=N;i+=(i&(-i))) bit[i]++;
}
int query(int x){
int ans=0;
for(int i=x+1;i>=1;i-=(i&(-i))) ans+=bit[i];
return ans;
}
int find_best(int n){
N=n;
for(int i=0;i<100;i++){
int pos=rand_int(0,n-1);
vector<int> cc=get(pos);
if(cc[1]==0) return pos;
Max=max(Max,cc[1]);
}
for(int i=0;i<n;i+=B){
vector<int> p;
for(int j=i;j<min(i+B,n);j++) p.push_back(j);
int cnt=0;
while(!p.empty()){
int x=p.back();p.pop_back();
vector<int> cc=get(x);
if(cc[1]==0) return x;
if(cc[1]<Max) update(x);
else{
cnt=cc[0]-query(x);
break;
}
}
while(cnt){
int l=0,r=(int)p.size()-1;
while(l<=r){
int mid=(l+r)>>1;
vector<int> cc=get(p[mid]);
if(cc[1]==0) return p[mid];
if(cc[1]<Max){
update(p[mid]);
p.erase(p.begin()+mid);
break;
}
if(cc[0]-query(p[mid])) r=mid-1;
else l=mid+1;
}
cnt--;
}
}
return -1;
}
