#include <holiday.h>
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
template <class an, class lyis>
bool minimize(an &x, const lyis y){
if(x > y){
x = y;
return true;
} else return false;
}
template <class an, class lyis>
bool maximize(an &x, const lyis y){
if(x < y){
x = y;
return true;
} else return false;
}
#define int ll
int n, s, d;
int a[maxn];
int res;
bool del[maxn];
void solve() {
int ans = 0, cur = 0;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
for (int i = s; i <= n; i++) {
q.push({a[i], -i}), cur += a[i];
while (q.size() > 0 && i - s + q.size() > d) {
cur -= q.top().first;
q.pop();
}
ans = max(cur, ans);
}
while (q.size() > 0) q.pop();
cur = 0;
priority_queue <int> pos;
memset(del, 0, sizeof(del));
for (int i = s; i <= n; i++) {
q.push({a[i], -i}), pos.push(i), cur += a[i];
while (q.size() > 0 && i - s + q.size() > d) {
pair <int, int> x = q.top();
q.pop();
cur -= x.first;
del[-x.second] = 1;
}
if (cur == ans) break;
}
while (pos.size() > 0) {
int x = pos.top();
if (del[x]) pos.pop(), del[x] = 0;
else break;
}
for (int i = s - 1, j = d - 1; i >= 1 && j >= 1; --i, --j) {
q.push({a[i], -i}), pos.push(i), cur += a[i];
while (q.size() > 0 && pos.top() - i + q.size() > j) {
pair <int, int> x = q.top();
q.pop();
cur -= x.first;
del[-x.second] = 1;
while (pos.size() > 0) {
int x = pos.top();
if (del[x]) pos.pop(), del[x] = 0;
else break;
}
}
ans = max(cur, ans);
}
maximize(res, ans);
}
int findMaxAttraction(int32_t N, int32_t S, int32_t D, int32_t attraction[]) {
s = S;
d = D;
n = N;
for (int i = 1; i <= n; i++) a[i] = attraction[i - 1];
++s;
solve();
reverse(a + 1, a + n + 1);
s = n - s + 1;
solve();
return res;
}
