#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long int findMaxAttraction(int n, int start, int d, int a[]) {
auto calc = [&](vector<ll> &v) -> pair<vector<ll>, vector<ll>> {
vector<ll> r(d+1), r2(d+1), pr(d+1, -1e18);
pr[0] = 0;
for (int i = 0; i < v.size(); i++) {
vector<ll> cur(d+1, -1e18);
for (int p = 0; p < d; p++) if (pr[p] != -1e18) {
cur[p+1] = max(cur[p+1], pr[p]);
r[p+1] = max(r[p+1], cur[p+1]);
if (p+1+i+1 <= d) r2[p+1+i+1] = max(r2[p+1+i+1], r[p+1]);
if (p+2 <= d) {
cur[p+2] = max(cur[p+2], pr[p]+v[i]);
r[p+2] = max(r[p+2], cur[p+2]);
}
if (p+2+i+1 <= d) r2[p+2+i+1] = max(r2[p+2+i+1], r[p+2]);
}
swap(cur, pr);
}
for (int i = 1; i < d+1; i++) r[i] = max(r[i], r[i-1]);
for (int i = 1; i < d+1; i++) r2[i] = max(r2[i], r2[i-1]);
return pair<vector<ll>, vector<ll>>{r, r2};
};
vector<ll> lcost, lcost2;
{
vector<ll> v;
for (int i = start-1; i >= 0; i--) v.push_back(a[i]);
auto [lc, lc2] = calc(v);
lcost = lc, lcost2 = lc2;
}
vector<ll> rcost, rcost2;
{
vector<ll> v;
for (int i = start+1; i < n; i++) v.push_back(a[i]);
auto [rc, rc2] = calc(v);
rcost = rc, rcost2 = rc2;
}
//cout << "lcost : "; for (ll x : lcost ) cout << x << " "; cout << endl;
//cout << "lcost2: "; for (ll x : lcost2) cout << x << " "; cout << endl;
//cout << "rcost : "; for (ll x : rcost ) cout << x << " "; cout << endl;
//cout << "rcost2: "; for (ll x : rcost2) cout << x << " "; cout << endl;
ll ans = 0;
for (int l = 0; l < d+1; l++) for (int take = 0; take < 2; take++) {
int r = d-l-take;
if (r < 0) continue;
ans = max({ans, take*a[start]+lcost[l]+rcost2[r], take*a[start]+lcost2[l]+rcost[r]});
//cout << l << " " << r << " take start " << take << endl;
//cout << take*a[start]<<" + "<<lcost[l]<<" + "<<rcost2[r] << endl;
//cout << take*a[start]<<" + "<<lcost2[l]<<" + "<<rcost[r] << endl;
}
return ans;
}
