#include"prize.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int N=2e5;
int fen[MAXN];
vector<int> w[MAXN];
vector<int> askk(int pos)
{
if(w[pos].empty()) return w[pos]=ask(pos);
return w[pos];
}
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>0;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> prel,vector<int> prer,int xl,int xr)
{
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=askk(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(!vl.empty()&&res[0]!=prel[0]+get(pos)-get(xl)) dnc(vl,val,prel,res,xl,pos);
if(!vr.empty()&&res[1]+get(xr)-get(pos)!=prer[1]) dnc(vr,val,res,prer,pos,xr);
break;
}
else update(pos,N,1);
}
}
vector<int> update(vector<int> idx)
{
int n=idx.size(),mx=0;
for(int i=0;(i<31||(i-31)*(i-31)<=n)&&i<n;i++)
{
vector<int> res=askk(idx[i]-1);
mx=max(mx,res[0]+res[1]);
}
dnc(idx,mx,{0,mx},{mx,0},0,n+1);
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);
vi=update(vi);
for(auto v:vi) if(askk(v-1)==(vector<int>){0,0}) return v-1;
}
