#include<bits/stdc++.h>
using namespace std;
long long findMaxAttraction(int n, int s, int d, int a[]) {
long long ans = 0;
long long now = 0;
int L = 0, R = -1;
vector<int> kt(n, 0);
priority_queue<pair<int, int>, vector<pair<int,int>> , greater<pair<int, int>>> pq;
priority_queue<pair<int, int>> smaller;
int sz = 0;
auto make_true = [&](int m) {
while (!pq.empty() && !smaller.empty()) {
auto x = pq.top();
auto y = smaller.top();
if (!kt[x.second]) {
pq.pop();
continue;
}
if (!kt[y.second]) {
smaller.pop();
continue;
}
if (x.first >= y.first) break;
pq.pop();
smaller.pop();
kt[x.second] = 2;
kt[y.second] = 1;
now += y.first - x.first;
pq.push(y);
smaller.push(x);
}
while (sz > m && !pq.empty()) {
auto x = pq.top();
pq.pop();
if (kt[x.second] != 1) continue;
kt[x.second] = 2;
now -= x.first;
smaller.push(x);
--sz;
}
while (sz < m && !smaller.empty()) {
auto x = smaller.top(); smaller.pop();
if (kt[x.second] != 2) continue;
kt[x.second] = 1;
now += x.first;
pq.push(x);
++sz;
}
};
auto add = [&](int id) {
int v = a[id];
pq.emplace(v, id);
now += v;
kt[id] = 1;
++sz;
};
auto del = [&](int id) {
int v = a[id];
if (kt[id] == 2) {
kt[id] = 0;
return ;
}
kt[id] = 0;
now -= v;
sz--;
};
auto moveL = [&](int l) {
while (L < l) del(L++);
while (L > l) add(--L);
};
auto moveR = [&](int r) {
while (R < r) add(++R);
while (R > r) del(R--);
};
function<void(int, int, int, int)> solve = [&](int l, int r, int L, int R) {
if (l > r) return ;
int mid = l + r >> 1;
int pos = -1;
moveR(L);
moveL(mid);
long long val = -1;
for (int i = L; i <= R; i++) {
moveR(i);
int lim = d - min(s - mid, i - s) - (i - mid);
make_true(lim);
if (val < now) {
val = now;
pos = i;
}
}
ans = max(ans, val);
assert(pos != -1);
solve(l, mid - 1, L, pos);
solve(mid + 1, r, pos, R);
};
solve(max(0, s - d), s, s, min(n - 1, s + d));
return ans;
}
