#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<int> vi;
const int MAXN = 100100;
ll a[MAXN];
int n;
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
n = N;
FOR(i, 0, n-1) a[i] = attraction[i];
ll ans = 0;
priority_queue<ll, vl, greater<ll>> q;
REP(2) {
FOR(le, 0, start) {
while (!q.empty()) {q.pop();}
int rem = d;
rem -= 2*(start-le);
if (rem <= 0) continue;
ll sum = 0;
FOR(i, le, start-1) {
q.push(a[i]);
sum += a[i];
}
// cout << " bef st sum = " << sum << endl;
FOR(i, start, n-1) {
q.push(a[i]);
sum += a[i];
// cout << " bef while sum = " << sum << endl;
while ((int)q.size() > rem) {
sum -= q.top();
// cout << " mined " << q.top() << endl;
q.pop();
}
// cout << " aft while sum = " << sum << endl;
ans = max(ans, sum);
//cout << " le = " << le << " start = " << start << " i = " << i << " sum = " << sum << endl;
rem--;
if (rem <= 0) break;
}
}
FOR(i, 0, n/2 - 1)
swap(a[i], a[n-1-i]);
start = n-1-start;
//FOR(i, 0, n-1) cout << " i = " << i << " a= " << a[i] << endl;
}
return ans;
}
