#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
ll findMaxAttraction(int N, int start, int d, int *A) {
ll ans = 0, sum = 0;
priority_queue<ll> pq;
ROF(i, start, max(0, start - d)) { // left then right
sum = 0;
while (size(pq))
pq.pop();
int j = i;
for (; j <= start; j++) {
pq.push(-A[j]);
sum += A[j];
}
while (size(pq) && size(pq) + start - i > d) {
sum += pq.top();
pq.pop();
}
ans = max(ans, sum);
for (; j < N; j++) {
pq.push(-A[j]);
sum += A[j];
while (size(pq) && size(pq) + j + start - 2 * i > d) {
sum += pq.top();
pq.pop();
}
if (j + start - 2 * i <= d)
ans = max(ans, sum);
}
}
ROF(i, start, max(0, start - d)) { // right then left
sum = 0;
while (size(pq))
pq.pop();
int j = i;
for (; j <= start; j++) {
pq.push(-A[j]);
sum += A[j];
}
while (size(pq) && size(pq) + start - i > d) {
sum += pq.top();
pq.pop();
}
ans = max(ans, sum);
for (; j < N; j++) {
pq.push(-A[j]);
sum += A[j];
while (size(pq) && size(pq) + j * 2 - start - i > d) {
sum += pq.top();
pq.pop();
}
if (size(pq) + j * 2 - start - i <= d)
ans = max(ans, sum);
}
}
return ans;
}
