#include"prize.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const int N=2e5;
const int K=500;
int fen[MAXN];
vector<int> w[MAXN],curr;
vector<int> askk(int pos)
{
if(w[pos].empty()) return w[pos]=ask(pos);
return w[pos];
}
void dnc(vector<int> vi,int val,vector<int> prel,vector<int> prer)
{
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!=prel) dnc(vl,val,prel,res);
if(!vr.empty()&&res!=prer) dnc(vr,val,res,prer);
break;
}
else curr.push_back(pos);
}
}
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]);
}
vector<int> res,pre;
for(int i=0;i<n;i++)
{
if(res.size()<K) res.push_back(idx[i]);
if(res.size()==K)
{
vector<int> nex=askk(res.back()-1);
if(nex[0]+nex[1]!=mx) curr.push_back(res.back()),res.pop_back();
else
{
if(nex!=pre) dnc(res,mx,pre,nex);
res.clear();
}
}
}
if(!res.empty()) dnc(res,mx,pre,askk(res.back()-1));
// dnc(idx,mx,{0,mx},{mx,0});
return curr;
}
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;
}
