#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define ins insert
#define pb push_back
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
int n;
int S;
int d;
vl w;
ll solverightonly(int L, int days){ //only move right from L
set<pair<ll, int>> taken;
ll ans = 0;
ll cursum = 0;
for(int i = L; i < n; i++){
int num = days-(i-L);
if(num <= 0) break;
if(sz(taken) > num){
assert(num == sz(taken)-1);
pair<ll, int> lowest = *(taken.begin());
taken.erase(lowest);
cursum-=lowest.f;
}
pair<ll, int> couldtake = mp(w[i], i);
if(sz(taken) < num){
taken.ins(couldtake);
cursum+=couldtake.f;
}
else{
pair<ll, int> lowest = *(taken.begin());
if(lowest.f < couldtake.f){
taken.erase(lowest);
cursum-=lowest.f;
taken.ins(couldtake);
cursum+=couldtake.f;
}
}
ckmax(ans, cursum);
}
return ans;
}
ll solve(){ //go left, then right
ll ans = 0;
for(int i = S; i >= 0; i--){
ckmax(ans, solverightonly(i, d-(S-i)));
}
return ans;
}
ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
n = _n;
S = start;
d = _d;
for(int i = 0; i < n; i++){
w.pb(attraction[i]);
}
if(start == 0){
return solverightonly(0, d);
}
ll ans = 0;
ckmax(ans, solve());
S = n-1-S;
reverse(all(w));
ckmax(ans, solve());
return ans;
}
