#include "holiday.h"
#include <bits/stdc++.h>
typedef long long ll;
#define debug(x) cerr << #x << ": " << x << endl;
#define sep ' '
const int MAXN = 2e5 + 10;
using namespace std;
ll A[MAXN], n;
namespace sack {
ll score = 0;
int len, d;
multiset<int> st;
vector<pair<int, vector<int>>> history;
inline void init(int d_) {
d = d_;
st.clear();
history.clear();
}
inline void add(int x) {
len++;
vector<int> er_vec;
st.insert(x);
score += x;
while (int(st.size()) > max(0, d - len + 1)) {
er_vec.push_back(*st.begin());
score -= *st.begin();
st.erase(st.begin());
}
history.push_back({x, er_vec});
}
inline void rollback() {
len--;
auto [x, y] = history.back();
history.pop_back();
for (int e : y) {
st.insert(e);
score += e;
}
st.erase(st.find(x));
score -= x;
}
inline void rollback(int k) {
while (k--) rollback();
}
}
ll divide(int l, int r, int optl, int optr) { // (r, optl]
if (r < l) return 0;
int mid = (l + r) >> 1;
for (int i = r; i >= mid; i--) sack::add(A[i]);
ll ans = sack::score, opt = optl;
for (int i = optl + 1; i <= optr; i++) {
sack::add(A[i]);
if (sack::score > ans) {
ans = sack::score;
opt = i;
}
}
sack::rollback(optr - optl);
ans = max(ans, divide(l, mid - 1, optl, opt));
sack::rollback(r - mid + 1);
for (int i = optl + 1; i <= opt; i++) sack::add(A[i]);
ans = max(ans, divide(mid + 1, r, opt, optr));
sack::rollback(opt - optl);
return ans;
}
inline ll solve(int n_, int start, int d, int attraction[]) {
memset(A, 0, sizeof A);
n = 0;
for (int i = 0; i < n_; i++) {
if (i > start) A[n++] = 0;
A[n++] = attraction[i];
}
sack::init(d);
return divide(max(0, start - d), start, start, min(ll(start + d), n - 1));
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
ll ans = solve(n, start, d, attraction);
reverse(attraction, attraction + n);
ans = max(ans, solve(n, n - 1 - start, d, attraction));
return ans;
}
