#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #include"holiday.h"
// #ifndef ONLINE_JUDGE
// #include "grader.cpp"
// #endif
const int N = 1e5 + 5;
ll c[N];
int d,start;
ll ans=0;
struct SegTree{
int n;
vector<pair<ll,int>> tree;
SegTree(int _n){
n = _n;
tree.resize(4 * n + 5);
}
pair<ll,int> mrge(pair<ll,int> a, pair<ll,int> b){
return {a.first+b.first , a.second+b.second};
}
void update(int node,int l,int r,int idx,ll val){
if(l == r) return tree[node] = {val , 1} , void();
int md = (l + r) >> 1;
idx <= md ? update(node<<1,l,md,idx,val) : update(node<<1|1,md+1,r,idx,val);
tree[node] = mrge(tree[node<<1] , tree[node<<1|1]);
}
ll query(int node,int l,int r,int k){
if(k <= 0) return 0;
if(tree[node].second <= k) return tree[node].first;
int md = (l + r) >> 1;
if(tree[node<<1].second >= k) return query(node<<1,l,md,k);
return tree[node<<1].first + query(node<<1|1,md+1,r,k-tree[node<<1].second);
}
void update(int idx,ll val){
update(1,1,n,idx+1,val);
}
ll query(int k){
return query(1,1,n,k);
}
};
void solve(int l,int r,int optl,int optr){
if(l > r || optl > optr) return;
int md = (l + r) >> 1;
pair<ll,ll> mx{-1e9,0};
vector<pair<ll,ll>> v;
for(int i=md;i<=optr;i++) v.push_back({-c[i],i});
sort(v.begin(),v.end());
SegTree sg((int)v.size());
for(int i=md;i<max(optl,md);i++){
int idx = lower_bound(v.begin(),v.end(),make_pair(-c[i],(ll)i)) - v.begin();
sg.update(idx,c[i]);
}
for(int i=max(optl,md);i<=optr;i++){
int rem = d - (min(abs(md-start),abs(i-start))+i-md);
int idx = lower_bound(v.begin(),v.end(),make_pair(-c[i],(ll)i)) - v.begin();
sg.update(idx,c[i]);
mx = max(mx , make_pair(sg.query(rem),-(ll)i));
}
ans = max(ans , mx.first);
solve(l,md-1,optl,-mx.second);
solve(md+1,r,-mx.second,optr);
}
long long int findMaxAttraction(int n, int s, int _d, int attraction[]) {
d = _d , start = s;
for(int i=0;i<n;i++) c[i] = attraction[i];
solve(0,n-1,0,n-1);
return ans;
}
