#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> calc(vector<int> cur) {
int n = cur.size();
int maxd = 2 * n + 1;
vector<pair<int, int>> helper;
for (int i = 0; i < n; i++) {
helper.emplace_back(cur[i], i);
}
sort(helper.rbegin(), helper.rend());
vector<int> loc(n);
for (int i = 0; i < n; i++)
loc[helper[i].second] = i;
vector<ll> dp(maxd + 1);
vector<int> to(maxd + 1);
vector<array<int, 4>> vpii;
vpii.push_back({0, maxd, 0, n});
while (!vpii.empty()) {
vector<int> ct(4 * n);
vector<ll> sum(4 * n);
int qin;
function<void(int, int, int)> upd = [&](int curin, int curl, int curr) {
if (qin > curr || qin < curl)
return;
if (curl == curr) {
ct[curin] = 1;
sum[curin] = helper[curl].first;
return;
}
upd(curin * 2 + 1, curl, (curl + curr) / 2);
upd(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
ct[curin] = ct[curin * 2 + 1] + ct[curin * 2 + 2];
sum[curin] = sum[curin * 2 + 1] + sum[curin * 2 + 2];
};
vector<array<int, 4>> vpii2;
int in = 0;
for (auto [l, r, mini, maxi] : vpii) {
int mid = (l + r) / 2;
auto calc = [&]() {
ll ans = 0;
int curin = 0, curl = 0, curr = n - 1;
int tmpct = mid - (in - 1);
while (curl != curr) {
if (ct[2 * curin + 1] >= tmpct) {
curin = curin * 2 + 1;
curr = (curl + curr) / 2;
} else {
ans += sum[curin * 2 + 1];
tmpct -= ct[curin * 2 + 1];
curin = curin * 2 + 2;
curl = (curl + curr) / 2 + 1;
}
}
if (tmpct >= 1 && ct[curin] >= 1) {
ans += sum[curin];
}
return ans;
};
while (in < maxi) {
ll ans = calc();
if (ans > dp[mid]) {
dp[mid] = ans;
to[mid] = in;
}
qin = loc[in];
upd(0, 0, n - 1);
in++;
}
ll ans = calc();
if (ans > dp[mid]) {
dp[mid] = ans;
to[mid] = in;
}
}
for (auto [l, r, mini, maxi] : vpii) {
int mid = (l + r) / 2;
if (l <= mid - 1) {
vpii2.push_back({l, mid - 1, mini, to[mid]});
}
if (mid + 1 <= r) {
vpii2.push_back({mid + 1, r, to[mid], maxi});
}
}
vpii.swap(vpii2);
}
return dp;
}
vector<ll> calc2(vector<int> cur) {
int n = cur.size();
int maxd = 3 * n + 1;
vector<pair<int, int>> helper;
for (int i = 0; i < n; i++) {
helper.emplace_back(cur[i], i);
}
sort(helper.rbegin(), helper.rend());
vector<int> loc(n);
for (int i = 0; i < n; i++)
loc[helper[i].second] = i;
vector<ll> dp(maxd + 1);
vector<int> to(maxd + 1);
vector<array<int, 4>> vpii;
vpii.push_back({0, maxd, 0, n});
while (!vpii.empty()) {
vector<int> ct(4 * n);
vector<ll> sum(4 * n);
int qin;
function<void(int, int, int)> upd = [&](int curin, int curl, int curr) {
if (qin > curr || qin < curl)
return;
if (curl == curr) {
ct[curin] = 1;
sum[curin] = helper[curl].first;
return;
}
upd(curin * 2 + 1, curl, (curl + curr) / 2);
upd(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
ct[curin] = ct[curin * 2 + 1] + ct[curin * 2 + 2];
sum[curin] = sum[curin * 2 + 1] + sum[curin * 2 + 2];
};
vector<array<int, 4>> vpii2;
int in = 0;
for (auto [l, r, mini, maxi] : vpii) {
int mid = (l + r) / 2;
auto calc = [&]() {
ll ans = 0;
int curin = 0, curl = 0, curr = n - 1;
int tmpct = mid - 2 * (in - 1);
while (curl != curr) {
if (ct[2 * curin + 1] >= tmpct) {
curin = curin * 2 + 1;
curr = (curl + curr) / 2;
} else {
ans += sum[curin * 2 + 1];
tmpct -= ct[2 * curin + 1];
curin = curin * 2 + 2;
curl = (curl + curr) / 2 + 1;
}
}
if (tmpct >= 1 && ct[curin] >= 1) {
ans += sum[curin];
}
return ans;
};
while (in < maxi) {
ll ans = calc();
if (ans > dp[mid]) {
dp[mid] = ans;
to[mid] = in;
}
qin = loc[in];
upd(0, 0, n - 1);
in++;
}
ll ans = calc();
if (ans > dp[mid]) {
dp[mid] = ans;
to[mid] = in;
}
}
for (auto [l, r, mini, maxi] : vpii) {
int mid = (l + r) / 2;
if (l <= mid - 1) {
vpii2.push_back({l, mid - 1, mini, to[mid]});
}
if (mid + 1 <= r) {
vpii2.push_back({mid + 1, r, to[mid], maxi});
}
}
vpii.swap(vpii2);
}
return dp;
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<int> right;
for (int i = start; i < n; i++) {
right.push_back(attraction[i]);
}
vector<int> left;
left.push_back(0);
for (int i = start - 1; i >= 0; i--) {
left.push_back(attraction[i]);
}
vector<ll> gor = calc(right), backr = calc2(right), gol = calc(left),
backl = calc2(left);
ll ans = 0;
for (int i = 0; i < min(d + 1, (int)gor.size()); i++) {
ans = max(ans, gor[i] + backl[min(d - i, (int)backl.size() - 1)]);
}
for (int i = 0; i < min(d + 1, (int)gol.size()); i++) {
ans = max(ans, gol[i] + backr[min(d - i, (int)backr.size() - 1)]);
}
return ans;
}
