#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int Z = 1e5;
int n, *a, d, o, C[Z], G[Z+1], L = 1, R;
i64 F[Z+1], ans;
void add(const int &j, const int &s) {
for(int i = 1 + C[j]; i <= n; i += i&-i) {
G[i] += s;
F[i] += s * a[j];
}
}
i64 get(int v) {
int i {}; i64 res {};
for(int j = 1<<17; j /= 2; ) if(i + j <= n && G[i + j] <= v) {
i += j;
res += F[i];
v -= G[i];
}
return res;
}
void reset(const int &l, const int &r) {
while(L > l) add(--L, +1);
while(R < r) add(++R, +1);
while(L < l) add(L++, -1);
while(R > r) add(R--, -1);
}
void dfs(int li, int ri, int lv, int rv) {
if(ri <= li) return;
int mi = (li + ri) / 2;
i64 best {};
int sv = max(mi, lv), mv = sv;
reset(mi, sv - 1);
for(int v = sv; v < rv; ++v) {
add(++R, 1);
i64 cur = get(max((int)(0), d - min(abs(o - mi), abs(o - v)) - (v - mi)));
if(cur > best) best = cur, mv = v;
}
ans = max(ans, best);
dfs(li, mi, lv, mv + 1);
dfs(mi + 1, ri, mv, rv);
}
i64 findMaxAttraction(int _n, int start, int _d, int _a[]) {
a = _a, n = _n, d = _d, o = start;
int byA[n];
iota(byA, byA + n, 0);
sort(byA, byA + n, [&](const int &i, const int &j) {
return a[i] > a[j];
});
for(int i = 0; i < n; ++i) C[byA[i]] = i;
dfs(0, n, 0, n);
return ans;
}
