#include "holiday.h"
#include "bits/stdc++.h"
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
namespace {
int N;
int start;
int D;
std::vector<int> A;
int dist(int l, int r) {
if (r < start) {
return start - l;
} else if (l <= start && start <= r) {
return r - l + std::min(start - l, r - start);
} else {
return r - start;
}
}
i64 sum = 0;
std::multiset<i64> pql;
std::multiset<i64, std::greater<i64>> pqr;
i64 balance(int x) {
x = std::max(0, x);
while (!pqr.empty() && !pql.empty() && *pqr.begin() > *pql.begin()) {
sum -= *pql.begin();
pqr.emplace(*pql.begin());
sum += *pqr.begin();
pql.emplace(*pqr.begin());
pql.erase(pql.begin());
pqr.erase(pqr.begin());
}
while (int(pql.size()) > x) {
sum -= *pql.begin();
pqr.emplace(*pql.begin());
pql.erase(pql.begin());
}
while (int(pql.size()) < x && !pqr.empty()) {
sum += *pqr.begin();
pql.emplace(*pqr.begin());
pqr.erase(pqr.begin());
}
return sum;
};
int l = 0, r = -1;
i64 fit(int L, int R) {
while (r < R) {
pqr.emplace(A[++r]);
}
while (l > L) {
pqr.emplace(A[--l]);
}
while (l < L) {
if (pql.find(A[l]) != pql.end()) {
sum -= A[l];
pql.erase(pql.find(A[l]));
} else {
pqr.erase(pqr.find(A[l]));
}
l++;
}
while (r > R) {
if (pql.find(A[r]) != pql.end()) {
sum -= A[r];
pql.erase(pql.find(A[r]));
} else {
pqr.erase(pqr.find(A[r]));
}
r--;
}
return balance(D - dist(l, r));
}
i64 ans = 0;
void dnq(int l, int r, int optl, int optr) {
if (l > r) {
return;
}
int mid = (l + r) >> 1;
std::pair<i64, int> res = {0, optl};
for (int i = optl; i <= std::min(optr, mid); ++i) {
res = std::max(res, std::pair<i64, int>{fit(i, mid), i});
}
ans = std::max(ans, res.first);
dnq(l, mid - 1, optl, res.second);
dnq(mid + 1, r, res.second, optr);
};
};
i64 findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
::start = start;
D = d;
A.resize(N);
for (int i = 0; i < N; ++i) {
A[i] = attraction[i];
}
dnq(0, n - 1, 0, n - 1);
return ans;
}
