#include<bits/stdc++.h>
#include"holiday.h"
using namespace std;
using ll=long long;
#pragma GCC optimize("O3")
const ll N=1e5+7;
ll A[N],a[N],br[N],opt[3*N],sol[3*N],frS[3*N],frO[3*N],On,NN,s,DD;
const ll N2=21*N;
int root[N],lc[N2],rc[N2],cnt[N2],nd;
ll sum[N2];
void bd(ll i,ll l=1,ll r=NN){
cnt[i]=sum[i]=0;
if(l==r)return;
ll md=(l+r)/2;
lc[i]=++nd;
rc[i]=++nd;
bd(lc[i],l,md);
bd(rc[i],md+1,r);
}
void upd(ll pr,ll tr,ll x,ll l=1,ll r=NN){
if(l==r){
cnt[tr]=cnt[pr]+1;
sum[tr]=sum[pr]+br[x];
return;
}
ll md=(l+r)/2;
if(x<=md){
rc[tr]=rc[pr];
lc[tr]=++nd;
upd(lc[pr],lc[tr],x,l,md);
}
else{
lc[tr]=lc[pr];
rc[tr]=++nd;
upd(rc[pr],rc[tr],x,md+1,r);
}
cnt[tr]=cnt[lc[tr]]+cnt[rc[tr]];
sum[tr]=sum[lc[tr]]+sum[rc[tr]];
}
ll qry(ll i,ll cc,ll l=1,ll r=NN){
if(cc<=0||!cnt[i])return 0;
if(cc>=cnt[i])return sum[i];
if(l==r)return(cc*br[l]);
ll md=(l+r)/2;
if(cc<=cnt[rc[i]])return qry(rc[i],cc,md+1,r);
else return sum[rc[i]]+qry(lc[i],cc-cnt[rc[i]],l,md);
}
void dnc(ll l,ll r,ll tl,ll tr){
if(l>r||tl>tr)return;
ll md=(l+r)/2;
opt[md]=tl;
sol[md]=qry(root[tl],md-tl+1);
for(int i=1+tl;i<=tr;++i){
ll qu=qry(root[i],md-i+1);
if(qu>sol[md]){
sol[md]=qu;
opt[md]=i;
}
}
dnc(l,md-1,tl,opt[md]);
dnc(md+1,r,opt[md],tr);
}
void _reset(){
map<ll,ll>mp;
set<ll>ss;
for(int i=1;i<=NN;++i)
ss.insert(a[i]);
ll CC=0;
for(ll x:ss){
mp[x]=++CC;
br[CC]=x;
}
for(int i=1;i<=NN;++i)
a[i]=mp[a[i]];
nd=0;
root[0]=++nd;
bd(root[0],1,NN);
for(int i=1;i<=NN;++i){
root[i]=++nd;
upd(root[i-1],root[i],a[i]);
}
}
void _test(){
cout<<qry(root[5],2)<<'\n';
cout<<qry(root[3],3)<<'\n';
cout<<qry(root[7],1)<<'\n';
cout<<qry(root[7],6)<<'\n';
}
ll findMaxAttraction(int _n,int _s,int _d,int _a[]){
On=_n,s=_s+1,DD=_d;
for(int i=0;i<_n;++i)A[1+i]=_a[i];
for(int i=s;i<=On;++i)
a[i-s+1]=A[i];
NN=On-s+1;
//assert(n>0);
if(NN<=0)return 0;
if(NN>0)_reset();
//_test();
if(NN>0)dnc(1,DD,1,NN);
for(int i=1;i<=DD;++i){
frS[i]=sol[i];
frO[i]=opt[i];
}
if(s==1)return*max_element(frS+1,frS+DD+1);
ll P=0;
for(int i=s-1;i>=1;--i){
a[++P]=A[i];
}
NN=P;
if(NN>0){
_reset();
dnc(1,DD,1,NN);
}
ll ans=0;
for(int i=1;i<=DD;++i){
ll d2=DD-i-frO[i];
ans=max(ans,frS[i]);
if(d2<=0)continue;
ans=max(ans,frS[i]+sol[d2]);
}
On=_n,s=_n-_s,DD=_d;
for(int i=0;i<_n;++i)A[1+i]=_a[_n-i-1];
for(int i=s;i<=On;++i)
a[i-s+1]=A[i];
NN=On-s+1;
if(NN>0)_reset();
//_test();
if(NN>0)dnc(1,DD,1,NN);
for(int i=1;i<=DD&&NN>0;++i){
frS[i]=sol[i];
frO[i]=opt[i];
}
if(s==1)return*max_element(frS+1,frS+DD+1);
P=0;
for(int i=s-1;i>=1;--i){
a[++P]=A[i];
}
NN=P;
if(NN>0){
_reset();
dnc(1,DD,1,NN);
}
for(int i=1;i<=DD;++i){
ll d2=DD-i-frO[i];
ans=max(ans,frS[i]);
if(d2<=0)continue;
ans=max(ans,frS[i]+sol[d2]);
}
return ans;
}
