#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> a[200000];
int ch[200000],ch2[200000],st[800001],f[200001];
void build(int node, int l, int r){
st[node]=r-l+1;
if (l==r)
return;
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
}
void update(int node, int l, int r, int i){
if (l>i||r<i)
return;
if (l==r){
st[node]=0;
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,i);
update(node<<1|1,mid+1,r,i);
st[node]=st[node<<1]+st[node<<1|1];
}
int get(int node, int l, int r, int u, int v){
if (l>v||r<u||l>r)
return 0;
if (l>=u&&r<=v)
return st[node];
int mid=(l+r)>>1;
return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v);
}
int get(int node, int l, int r, int x){
if (l==r)
return l;
int mid=(l+r)>>1;
return (st[node<<1]>=x?get(node<<1,l,mid,x):get(node<<1|1,mid+1,r,x-st[node<<1]));
}
void query(int i){
if (a[i].empty())
a[i]=ask(i);
}
void update(int i){
ch2[i]=1;
i++;
for (;i<=200000;i+=i&(-i))
f[i]++;
}
int get(int i){
i++;
int res=0;
for (;i;i-=i&(-i))
res+=f[i];
return res;
}
int b[4]={1,5,26,472};
int best(vector <int> v, int idx){
memset(ch,0,sizeof(ch));
memset(ch2,0,sizeof(ch2));
memset(f,0,sizeof(f));
if (v.size()==1)
return v[0];
if (v.size()<b[idx]){
for (int i=0;i<v.size();i++){
query(v[i]);
if (!a[v[i]][0]&&!a[v[i]][1])
return v[i];
}
}
int n=v.size(),mx=0;
build(1,0,n-1);
for (int i=0;i<b[idx];i++){
query(v[i]);
if (!a[v[i]][0]&&!a[v[i]][1])
return v[i];
mx=max(mx,a[v[i]][0]+a[v[i]][1]);
}
int cur=0;
for (int i=0;i<b[idx];i++){
update(1,0,n-1,i);
if (a[v[i]][0]+a[v[i]][1]==mx){
cur=i;
break;
}
else
update(i);
}
priority_queue <int, vector <int>, greater <int>> q;
vector <int> v2;
while (true){
while (!q.empty()){
if (a[v[q.top()]][0]==get(q.top())){
cur=q.top();
q.pop();
}
else
break;
}
vector <int> ve;
int l=1,r=get(1,0,n-1,cur,(q.empty()?n-1:q.top()-1)),val=get(1,0,n-1,0,cur-1);
if (!q.empty()&&q.top()-cur-1==a[v[q.top()]][0]-a[v[cur]][0]){
for (int i=cur+1;i<q.top();i++){
v2.push_back(i);
update(1,0,n-1,i);
if (!ch2[i])
update(i);
}
continue;
}
while (l<=r){
int mid=(l+r)>>1;
int pos=get(1,0,n-1,val+mid);
query(v[pos]);
ve.push_back(pos);
if (!a[v[pos]][0]&&!a[v[pos]][1])
return v[pos];
if (a[v[pos]][0]+a[v[pos]][1]==mx){
if (a[v[pos]][0]>get(pos)){
if (!ch[pos])
q.push(pos);
ch[pos]=1;
r=mid-1;
}
else{
cur=pos;
break;
}
continue;
}
update(pos);
v2.push_back(pos);
break;
}
for (int i:ve)
update(1,0,n-1,i);
}
sort(v2.begin(),v2.end());
v2.resize(unique(v2.begin(),v2.end())-v2.begin());
return best(v2,idx-1);
}
int find_best(int n){
vector <int> v;
for (int i=0;i<n;i++)
v.push_back(i);
return best(v,3);
}
