#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
const int INF = 1e9 + 7;
const int maxn = 1e5 + 10;
int n, s, d, a[maxn];
int calc_dist(int l, int r){
if (l >= s) return r - s;
if (r <= s) return s - l;
return r - l + min(r - s, s - l);
}
ll solve(){
// cout << "kore wa beginning" << endl;
// cout << n << ' ' << ' ' << s << ' ' << d << endl;
set<pii> include, removed; ll best = 0, include_sum = 0;
for (int i = 0; i < s; i++){
removed.insert({a[i], i});
}
int l = 0;
for (int r = s; r < min(s + d, n); r++){
// cout << l << ' ' << r << endl;
removed.insert({a[r], r});
while (calc_dist(l, r) > d){
if (include.count({a[l], l})){
include.erase({a[l], l});
include_sum -= a[l];
}
else removed.erase({a[l], l});
l++;
}
// rebalance
while (include.size() > 0 && removed.size() > 0 &&
include.begin()->F < removed.rbegin()->F){
pii x = *include.begin(), y = *removed.rbegin();
include_sum -= x.F; include.erase(x);
removed.erase(y);
include_sum += y.F; include.insert(y);
removed.insert(x);
}
// adding elements if we can
int can_include = d - calc_dist(l, r);
while (include.size() < can_include && removed.size() > 0){
pii x = *removed.rbegin(); removed.erase(x);
include_sum += x.F; include.insert(x);
}
// removing elements if we must
while (include.size() > can_include){
pii x = *include.begin(); include.erase(x);
include_sum -= x.F; removed.insert(x);
}
while (l < s){
int can_include = d - calc_dist(l, r);
int can_include_prime = d - calc_dist(l + 1, r);
ll delta = 0;
if (include.count({a[l], l})){
delta -= a[l];
can_include_prime++;
}
else{
removed.erase({a[l], l});
}
auto it = removed.rbegin();
vector<pii> to_remove;
FOR(_, min((int)removed.size(), can_include_prime - can_include)){
to_remove.push_back(*it);
delta += it->F; it++;
}
if (delta < 0 && include.count({a[l], l})) break;
if (include.count({a[l], l})){
include.erase({a[l], l});
}
for (auto x : to_remove){
removed.erase(x);
include.insert(x);
}
include_sum += delta; l++;
}
best = max(best, include_sum);
}
return best;
}
ll findMaxAttraction(int N, int start, int D, int attraction[]){
n = N, s = start, d = D;
for (int i = 0; i < n; i++) a[i] = attraction[i];
ll re = solve();
reverse(a, a + n); s = n - 1 - start;
// re = max(re, solve());
return re;
}
