#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];
ll cost(int l,int r,int d){
vector<int> v;
for(int i=l;i<=r;i++) v.push_back(c[i]);
sort(v.rbegin(),v.rend());
ll ret = 0;
for(int i=0;i<min((int)v.size(),d);i++) ret += v[i];
return ret;
}
int d,start;
ll ans=0;
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);
mx = max(mx , make_pair(cost(md,i,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];
// for(int l=0;l<n;l++){
// pair<ll,ll> mx{-1e9,0};
// for(int r=l;r<n;r++){
// int rem = d - (min(abs(l-start),abs(r-start))+r-l);
// mx = max(mx , make_pair(cost(l,r,rem),-(ll)r));
// }
// ans = max(ans , mx.first);
// assert(-mx.second>=prv);
// prv = -mx.second;
// }
solve(0,n-1,0,n-1);
return ans;
}
