#include<bits/stdc++.h>
using namespace std;
struct Eins {
struct node {
long long val = 0;
int cnt = 0;
int lef = -1, rig = -1;
};
vector<node> st;
int n;
int count = 0;
Eins(int n) : n(n) {
st.resize(31 * n + 1);
}
void modify(int&id, int l, int r, int pos, int val) {
if (id == -1) id = ++count;
if (l == r) {
st[id].val += pos * val;
st[id].cnt += val;
return ;
}
int mid = l + r >> 1;
if (pos <= mid) modify(st[id].lef, l, mid, pos, val);
else modify(st[id].rig, mid + 1, r, pos, val);
st[id].val = st[id].cnt = 0;
if (st[id].lef != -1) {
st[id].val += st[st[id].lef].val;
st[id].cnt += st[st[id].lef].cnt;
}
if (st[id].rig != -1) {
st[id].val += st[st[id].rig].val;
st[id].cnt += st[st[id].rig].cnt;
}
}
long long get(int id, int l, int r, int& num) {
if (id == -1) return 0;
if (num >= st[id].cnt) {
num -= st[id].cnt;
return st[id].val;
}
if (l == r) return 0;
int mid = l + r >> 1;
return get(st[id].rig, mid + 1, r, num) + get(st[id].lef, l, mid, num);
}
};
long long findMaxAttraction(int n, int s, int d, int a[]) {
long long ans = 0;
int L = 0, R = -1;
Eins Tree(n);
const int maxN = (int) 1e9;
int root = 0;
auto add = [&](int id) {
Tree.modify(root, 0, maxN, a[id], 1);
};
auto del = [&](int id) {
Tree.modify(root, 0, maxN, a[id], -1);
};
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);
long long now = Tree.get(0, 0, maxN, 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;
}
