#include <vector>
#include <algorithm>
using namespace std;
struct SegmentTree {
vector<int> attractions;
vector<long long> prefixSum;
SegmentTree(vector<int> arr) {
sort(arr.begin(), arr.end(), greater<int>());
attractions = arr;
prefixSum.resize(arr.size() + 1, 0);
for (int i = 0; i < arr.size(); ++i) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
}
long long query(int k) {
if (k <= 0) return 0;
k = min(k, (int)prefixSum.size() - 1);
return prefixSum[k];
}
};
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
if (d == 0) return 0;
vector<int> left, right;
for (int i = start - 1; i >= 0; --i) left.push_back(attraction[i]);
for (int i = start + 1; i < n; ++i) right.push_back(attraction[i]);
SegmentTree leftTree(left), rightTree(right);
long long maxAtt = 0;
// Case 1: Visit start first
if (d >= 1) {
maxAtt = attraction[start];
}
// Explore left then right
for (int a = 0; a <= left.size(); ++a) {
// Days used: a (move left) + 1 (visit start) + 2*b (move and visit right)
int daysUsed = a + 1;
if (daysUsed > d) continue;
int remaining = d - daysUsed;
int maxB = min(remaining / 2, (int)right.size());
long long current = attraction[start] + leftTree.query(a) + rightTree.query(maxB);
maxAtt = max(maxAtt, current);
}
// Explore right then left
for (int b = 0; b <= right.size(); ++b) {
int daysUsed = b + 1;
if (daysUsed > d) continue;
int remaining = d - daysUsed;
int maxA = min(remaining / 2, (int)left.size());
long long current = attraction[start] + rightTree.query(b) + leftTree.query(maxA);
maxAtt = max(maxAtt, current);
}
// Consider visiting only left or only right
for (int a = 0; a <= left.size(); ++a) {
int daysNeeded = a + (a > 0 ? 1 : 0); // Move a steps + visit start if a > 0
if (daysNeeded > d) continue;
int remaining = d - daysNeeded;
long long current = (a > 0 ? attraction[start] : 0) + leftTree.query(a);
maxAtt = max(maxAtt, current);
}
for (int b = 0; b <= right.size(); ++b) {
int daysNeeded = b + (b > 0 ? 1 : 0);
if (daysNeeded > d) continue;
int remaining = d - daysNeeded;
long long current = (b > 0 ? attraction[start] : 0) + rightTree.query(b);
maxAtt = max(maxAtt, current);
}
return maxAtt;
}
