#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <class F, class S>
bool chmax(F &u, const S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
long long int findMaxAttraction(int n, int s, int d, int attraction[]) {
vector <i64> a(n);
for ( int i = 0; i < n; i++ ) a[i] = attraction[i];
i64 opt = 0;
for ( int l = 0; l <= s; l++ ){
multiset <i64> B, A;
for ( int i = l; i < s; i++ ) B.insert(a[i]);
i64 cnt = 0;
for ( int r = s; r < n; r++ ){
int step = r - l + min(s - l, r - s);
B.insert(a[r]);
while ( !B.empty() && (int)A.size() + step < d ){
auto it = --B.end(); B.erase(it);
A.insert(*it); cnt += *it;
}
while ( !A.empty() && (int)A.size() + step > d ){
auto it = A.begin(); A.erase(it);
B.insert(*it); cnt -= *it;
}
if ( !A.empty() && !B.empty() ){
while ( *A.begin() < *B.rbegin() ){
auto x = *A.begin(); A.erase(A.find(x));
auto y = *B.rbegin(); B.erase(B.find(y));
cnt += y - x;
A.insert(y), B.insert(x);
}
}
chmax(opt, cnt);
}
}
return opt;
}
