#include<bits/stdc++.h>
#include <holiday.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,m,k,a[maxn],b[maxn],c[maxn],cur,S,opt[maxn],d,dp[maxn][2][3];
int ST[4*maxn],sum[4*maxn];
void update(int id,int cl,int cr,int pos,int val)
{
if(cl>pos||cr<pos) return;
if(cl==cr)
{
ST[id]=1;
sum[id]=val;
return;
}
int mid=(cl+cr)/2;
if(pos<=mid) update(2*id,cl,mid,pos,val);
else update(2*id+1,mid+1,cr,pos,val);
ST[id]=ST[id*2]+ST[id*2+1];
sum[id]=sum[id*2]+sum[id*2+1];
}
int get(int id,int cl,int cr,int k)
{
if(k<=0) return 0;
if(ST[id]<=k) return sum[id];
int mid=(cl+cr)/2;
if(ST[2*id]<=k) return sum[id*2]+get(id*2+1,mid+1,cr,k-ST[id*2]);
else return get(2*id,cl,mid,k);
}
struct seg
{
int l,r,optl,optr;
};
void dnc(int l,int r,int rev,int jump)
{
if(l>r) return;
queue<seg> q;
q.push({0,d,l,r});
int scan=l-1;
for(int i=1;i<=4*n;i++)
{
ST[i]=sum[i]=0;
}
while(!q.empty())
{
seg x=q.front();
q.pop();
// cout<<x.l<<" "<<x.r<<" "<<x.optl<<" "<<x.optr<<"\n";
int mid=(x.l+x.r)/2;
dp[mid][rev][jump]=0;
opt[mid]=x.optl;
if(scan>x.optl)
{
for(int i=1;i<=4*n;i++)
{
ST[i]=sum[i]=0;
}
scan=l-1;
}
while(scan<x.optl)
{
++scan;
update(1,1,n,c[scan],a[scan]);
}
for(int i=x.optl;i<=x.optr;i++)
{
update(1,1,n,c[i],a[i]);
int d=i-l+1;
int kk=get(1,1,n,mid-d*jump);
if(kk>=dp[mid][rev][jump])
{
dp[mid][rev][jump]=kk;
opt[mid]=i;
}
}
scan=x.optr;
// cout<<mid<<" "<<dp[mid][rev][jump]<<"\n";
if(x.l<mid) q.push({x.l,mid-1,x.optl,opt[mid]});
if(x.r>mid) q.push({mid+1,x.r,opt[mid],x.optr});
}
}
bool cmp(int x,int y)
{
return a[x]>a[y];
}
long long findMaxAttraction(int32_t _n,int32_t start,int32_t _d,int32_t _a[])
{
for(int i=0;i<_n;i++)
{
a[i+1]=_a[i];
b[i+1]=i+1;
}
d=_d;
n=_n;
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
{
c[b[i]]=i;
}
// for(int i=1;i<=n;i++)
// {
// cout<<c[i]<<" ";
// update(1,1,n,c[i],a[i]);
// }
// cout<<"\n";
// for(int i=1;i<=4*n;i++)
// {
// cout<<ST[i]<<" ";
// }
// cout<<"\n";
// cout<<get(1,1,n,3)<<"\n";
S=++start;
dnc(S+1,n,0,1);
dnc(S+1,n,0,2);
for(int i=1;i<=n/2;i++)
{
swap(c[i],c[n+1-i]);
swap(a[i],a[n+1-i]);
}
S=n+1-S;
dnc(S+1,n,1,1);
dnc(S+1,n,1,2);
int ans=0;
for(int i=0;i<=d;i++)
{
ans=max(dp[i][0][1]+dp[d-i][1][2],ans);
ans=max(dp[i][1][1]+dp[d-i][0][2],ans);
if(i<d)
{
ans=max(ans,dp[i][0][1]+dp[d-i-1][1][2]+a[S]);
ans=max(ans,dp[i][1][1]+dp[d-i-1][0][2]+a[S]);
}
}
// for(int i=0;i<=d;i++)
// {
// cout<<dp[i][1][1]<<" ";
// }
// cout<<"\n";
return ans;
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
// int32_t a[]={10,2,20,40,30,1,32,15};
// cout<<findMaxAttraction(8,4,7,a);
//}
