#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
ll res = 0;
vector<int> a(n);
for(int i = 0 ; i < n ; i++)
a[i] = attraction[i];
for(int t = 0 ; t < 2 ; t++) {
for(int i = start ; i >= 0 ; i--) {
ll sum = 0;
multiset<int> S;
int d2 = d - (start - i);
for(int j = i ; j < n ; j++) {
S.insert(a[j]);
sum += a[j];
//~ cout << i << " " << j << " " << d2 - (j - i ) << endl;
while(!S.empty() && (int)S.size() > d2 - (j - i)) {
auto it = S.begin();
sum -= *it;
S.erase(it);
}
//~ cout << sum << " " << S.size() << " " << d2 - (j - i ) << endl;
res = max(res, sum);
}
}
if(n > 3000)
break;
reverse(a.begin(), a.end());
start = n - start - 1;
}
return res;
}
