#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define first X
#define second Y
#define eb emplace_back
#define ALL(i) i.begin(),i.end()
#define SZ(i) int(i.size())
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream &__printRng (ostream& os, IT bg, IT ed) {
for (IT it=bg; it!=ed; it++) {
if (it == bg) os << "{" << *it;
else os << "," << *it;
}
return os << "}";
}
template<typename T> ostream &operator << (ostream& os, const vector<T> &vec) {
return __printRng(os,ALL(vec));
}
#else
#define debug(...)
#endif
#include"holiday.h"
struct KSum {
int k = 0, ptr = 0;
multiset<int> mx;
multiset<int> mn;
ll sum = 0;
void inc () {
assert(mn.size());
auto ptr = prev(mn.end());
mx.insert(*ptr);
sum += *ptr;
mn.erase(ptr);
k++;
}
void dec () {
assert(mx.size());
auto ptr = mx.begin();
mn.insert(*ptr);
sum -= *ptr;
mx.erase(ptr);
k--;
}
void add (int val) {
mn.insert(val);
if (mx.size()) {
dec();
inc();
}
}
};
ll solve (int n, int s, int d, vector<int> a) {
if (d == 0) return 0;
vector<int> sg;
sg.eb(0);
for (int i=s+1; i<n; i++) {
sg.eb(a[i]);
}
for (int i=0; i<d+13; i++) {
sg.eb(0);
}
vector<ll> msg(d+1, 0);
KSum l, r;
l.add(sg[1]);
r.add(sg[1]);
r.add(sg[2]);
int bst = 1;
for (int i=2; i<=d; i++) {
while (l.k < bst && l.k+bst < i) {
l.inc();
}
while (r.k < bst+1 && r.k+bst+1 < i) {
r.inc();
}
while (bst + 2 <= SZ(sg) && r.sum >= l.sum) {
l.add(sg[++bst]);
r.add(sg[bst+1]);
if (l.k) {
l.dec();
}
if (r.k) {
r.dec();
}
debug(bst, l.sum, r.sum);
while (l.k < bst && l.k+bst < i) {
l.inc();
}
while (r.k < bst+1 && r.k+bst+1 < i) {
r.inc();
}
}
debug(l.k, bst);
msg[i] = l.sum;
}
debug(sg, msg);
return max(a[s] + msg[d-1], msg[d]);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<int> a;
for (int i=0; i<n; i++) {
a.eb(attraction[i]);
}
ll la = solve(n, start, d, a);
reverse(ALL(a));
ll ra = solve(n, n-1-start, d, a);
return max(la, ra);
}
