#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> a;
ll solve(int s, int d, bool l){
ll res = 0;
int k = d+1;
multiset<int> best;
ll cur = 0;
int x = 1;
if (l) x = -1;
for (int i=0; abs(i)<d; i+=x){
if (s+i >= n || s+i < 0) break;
k--;
if (best.size() < k || a[s+i] > *best.begin()){
best.insert(a[s+i]);
cur += a[s+i];
}
while (best.size() > k){
cur -= *best.begin();
best.erase(best.begin());
}
res = max(res, cur);
}
return res;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]){
::n = n;
a.resize(n);
for (int i=0; i<n; i++) a[i] = attraction[i];
if (start == 0) return solve(0, d, false);
ll res = 0;
for (int i=0; i<d; i++){
if (start+i < n) res = max(res, solve(start+i, d-i, true));
if (start-i >= 0) res = max(res, solve(start-i, d-i, false));
}
return res;
}
