#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;
void init(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,int x){
if(l == r) return tree[node] = {val , x} , void();
int md = (l + r) >> 1;
idx <= md ? update(node<<1,l,md,idx,val,x) : update(node<<1|1,md+1,r,idx,val,x);
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,int x){
update(1,1,n,idx+1,val,x);
}
ll query(int k){
return query(1,1,n,k);
}
} sg;
vector<pair<ll,ll>> v;
int curL=1,curR=0;
void add(int idx){
int id = lower_bound(v.begin(),v.end(),make_pair(-c[idx],(ll)idx)) - v.begin();
// cout<<"+ "<<idx<<" "<<id<<endl;
sg.update(id,c[idx],1);
}
void rem(int idx){
int id = lower_bound(v.begin(),v.end(),make_pair(-c[idx],(ll)idx)) - v.begin();
// cout<<"- "<<idx<<" "<<id<<endl;
sg.update(id,0,0);
}
ll cost(int l,int r,int k){
// cout<<curL<<" "<<curR<<endl;
while(curL > l) curL -- , add(curL);
while(curR < r) curR ++ , add(curR);
while(curL < l) rem(curL) , curL ++;
while(curR > r) rem(curR) , curR --;
// cout<<l<<" "<<r<<" "<<k<<" = "<<sg.tree[1].first<<endl;
return sg.query(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};
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();
mx = max(mx , make_pair(cost(md,i,rem),-(ll)i));
}
// if(mx.first == 9) cout<<md<<" "<<mx.second<<endl;
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];
sg.init(n);
for(int i=0;i<n;i++) v.push_back({-c[i],i});
sort(v.begin(),v.end());
solve(0,n-1,0,n-1);
add(0);
return ans;
}
