#include"prize.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int N=2e5;
int fen[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
int walk(int n,int val) { int ans=0;for(int i=getlog(n);i+1;i--) if(ans+(1<<i)<=n&&val>=fen[ans+(1<<i)]) val-=fen[ans+=(1<<i)];return ans+1; }
void dnc(vector<int> vi,int val)
{
vector<int> vv;
int l=0,r=vi.size()-1;
for(int i=0;i<vi.size();i++) if(i%2==0) vv.push_back(vi[l++]);
else vv.push_back(vi[r--]);
while(!vv.empty())
{
int pos=vv.back();
vv.pop_back();
vector<int> res=ask(pos-1);
if(res[0]+res[1]==val)
{
vector<int> vl,vr;
for(int i=0;i<vv.size();i++) if(i%2==0) vl.push_back(vv[i]);
else vr.push_back(vv[i]);
reverse(vr.begin(),vr.end());
if(res[0]!=get(pos-1)&&!vl.empty()) dnc(vl,val);
if(res[1]!=get(N)-get(pos)&&!vr.empty()) dnc(vr,val);
break;
}
else update(pos,N,1);
}
}
vector<int> update(vector<int> idx)
{
int n=idx.size(),mx=0;
for(int i=0;i*i<=n&&i<n;i++)
{
vector<int> res=ask(idx[i]-1);
mx=max(mx,res[0]+res[1]);
}
dnc(idx,mx);
vector<int> ans;
while(walk(N,0)!=N+1) ans.push_back(walk(N,0)),update(walk(N,0),N,-1);
return ans;
}
int find_best(int n)
{
vector<int> vi;
for(int i=1;i<=n;i++) vi.push_back(i);
while(vi.size()>1) vi=update(vi);
if(vi.empty()) return -1;
return vi[0]-1;
}
