#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.bein())
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define pb emplace_back
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
int find_best(int n) {
function<vi(vi,ll,ll,ll)> sol=[&](vi v,ll L,ll R,ll S){
vi res;
if(S==0)return res;
if(v.size()==S)return v;
ll md=v.size()/2;
vi srt(v.size());rep(i,v.size())srt[i]=i;
sort(all(srt),[&](ll a,ll b){if(abs(a-md)==abs(b-md))return a<b;return abs(a-md)<abs(b-md);});
vb done(v.size(),false);
for(ll tt:srt){
ll i=v[tt];done[tt]=true;
auto tmp=ask(i);
tmp[0]-=L;tmp[1]-=R;
for(ll x:res)tmp[x>i]--;
if(tmp[0]+tmp[1]!=S-res.size())res.pb(i);
else{
vi va,vb;
rep(j,v.size())if(!done[j]){
if(v[j]<i)va.pb(v[j]);
else vb.pb(v[j]);
}
vi ra=sol(va,L,R+res.size()+tmp[1],tmp[0]);
vi rb=sol(vb,L+res.size()+tmp[0],R,tmp[1]);
for(ll x:ra)res.pb(x);
for(ll x:rb)res.pb(x);
break;
}
}
return res;
};
vi al(n);rep(i,n)al[i]=i;
while(al.size()>1){
ll ma=0;
ll tmp=0;
ll cur=al.size();
while(cur>1){
tmp+=(ll)(sqrt(cur)*0.95);
cur=sqrt(cur);
}
rep(i,min((ll)(al.size()),tmp)){
auto tmp=ask(al[i]);
chmax(ma,(ll)(tmp[0]+tmp[1]));
}
vi nal=sol(al,0,0,ma);
al=nal;
}
return al[0];
}
