#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "holiday.h"
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
VI a;
rep(i, n) a.pb(attraction[i]);
if (start == 0) {
ll ans = 0;
priority_queue<int> pq;
ll cur = 0;
rep(i, min(d, n)) {
pq.push(-a[i]);
cur += a[i];
while (pq.size() > d-i) {
cur += pq.top();
pq.pop();
}
setmax(ans, cur);
}
return ans;
} else {
ll ans = 0;
int D = d;
function<ll(int)> f[2];
f[0] = [&](int s)->ll {
int d = D - (start - s);
priority_queue<int> pq;
ll curmax = 0;
ll cur = 0;
for (int i = 0; i < d && s + i < n; i++) {
pq.push(-a[s + i]);
cur += a[s + i];
while (pq.size() > d-i) {
cur += pq.top();
pq.pop();
}
setmax(ans, cur);
setmax(curmax, cur);
}
return curmax;
};
f[1] = [&](int s)->ll {
int d = D - (s - start);
priority_queue<int> pq;
ll cur = 0;
ll curmax = 0;
for (int i = 0; i < d && s - i >= 0; i++) {
pq.push(-a[s - i]);
cur += a[s - i];
while (pq.size() > d-i) {
cur += pq.top();
pq.pop();
}
setmax(ans, cur);
setmax(curmax, cur);
}
return curmax;
};
/*reprl(s, start, 0) {*/
/* ll cur = f[0](s);*/
/* setmax(ans, cur);*/
/* cout << cur << endl;*/
/*}*/
/*cout << "---" << endl;*/
/*replr(s, start, n-1) {*/
/* ll cur = f[1](s);*/
/* setmax(ans, cur);*/
/* cout << cur << endl;*/
/*}*/
/*cout << "---" << endl;*/
rep(fi, 2) {
int l, r;
if (fi == 0) {
l = 0;
r = start;
} else {
l = start;
r = n-1;
}
while (l+1 < r) {
int m = (l+r)/2;
ll al = f[fi](m);
ll ar = f[fi](m+1);
if (al < ar) l = m+1;
else if (al > ar) r = m;
else {
l = m;
r = m+1;
break;
}
}
setmax(ans, f[fi](l));
setmax(ans, f[fi](r));
}
return ans;
}
return 0;
}
