#include"prize.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int N=2e5;
int fen[MAXN],ans;
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
{
if(res==(vector<int>){0,0}) ans=pos-1;
update(pos,N,1);
}
}
}
int find_best(int n)
{
vector<int> vi;
for(int i=1;i<=n;i++) vi.push_back(i);
int mx=0;
for(int i=0;(i<31||(i-31)*(i-31)<=vi.size())&&i<vi.size();i++)
{
vector<int> res=askk(vi[i]-1);
mx=max(mx,res[0]+res[1]);
}
dnc(vi,mx,{0,mx},{mx,0},0,n+1);
return ans;
}
