#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, d;
vector<int> a;
vector<ll> l1, l2, r1, r2;
void solve(int s, int k, vector<ll>& dp){
dp[0] = 0;
vector<int> opt(d+1);
opt[0] = s;
for (int j=16; j>=0; j--){
ll cur = 0;
priority_queue<ll> in, out;
out.push(a[s]);
for (int i=1<<j; i<=d; i+=1<<(j+1)){
int l = opt[i-(1<<j)], r = i+(1<<j) <= d ? opt[i+(1<<j)] : n-1;
pair<ll,int> bsf = {0, s};
for (int loc=l; loc<=r; loc++){
if (loc != l) out.push(a[loc]);
int vis = i-k*(loc-s);
if (vis < 0) continue;
while (in.size() < vis && !out.empty()){
in.push(-out.top());
cur += out.top();
out.pop();
}
while (in.size() > vis){
cur += in.top();
out.push(-in.top());
in.pop();
}
while (!in.empty() && !out.empty() && -in.top() < out.top()){
cur += in.top();
cur += out.top();
out.push(-in.top());
in.pop();
in.push(-out.top());
out.pop();
}
bsf = max(bsf, {cur, loc});
}
dp[i] = bsf.first;
opt[i] = bsf.second;
}
}
}
ll findMaxAttraction(int n, int start, int d, int attraction[]){
::n = n;
::d = d;
a.resize(n);
for (int i=0; i<n; i++) a[i] = attraction[i];
r1.resize(d+1);
r2.resize(d+1);
l1.resize(d+1);
l2.resize(d+1);
solve(start, 1, r1);
solve(start, 2, r2);
a[start] = 0;
reverse(a.begin(), a.end());
start = n-1-start;
solve(start, 1, l1);
solve(start, 2, l2);
ll res = 0;
for (int i=0; i<=d; i++) res = max(res, max(l2[i]+r1[d-i], l1[i]+r2[d-i]));
return res;
}
