#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 (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 = 0;
for (int i = L; i <= R; i++) {
moveR(i);
make_true(d - min(s - mid, i - s) - (i - mid));
if (val < now) {
val = now;
pos = i;
}
}
ans = max(ans, val);
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;
}
/*int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a[] = {10, 2, 20, 30, 1};
cout << findMaxAttraction(5, 2, 7, a);
}*/
