#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const long long inf = 1e18;
int n, d, start;
int a[N], rk[N], cnt[4 * N];
long long s[4 * N];
bool on[N];
long long qry(int k, int id = 1, int l = 0, int r = n - 1) {
if (l == r) {
return s[id];
}
int m = (l + r) / 2;
return k > cnt[id * 2] ? qry(k - cnt[id * 2], id * 2 + 1, m + 1, r) + s[id * 2] : qry(k, id * 2, l, m);
}
void pul(int id) {
cnt[id] = cnt[id * 2] + cnt[id * 2 + 1];
s[id] = s[id * 2] + s[id * 2 + 1];
}
void upd(int i, int x, int id = 1, int l = 0, int r = n - 1) {
if (l == r) {
s[id] = x;
cnt[id] = bool(x);
return;
}
int m = (l + r) / 2;
if (i <= m) {
upd(i, x, id * 2, l, m);
} else {
upd(i, x, id * 2 + 1, m + 1, r);
}
pul(id);
}
void tog(int i) {
on[i] ^= 1;
upd(rk[i], on[i] ? a[i] : 0);
}
int L = 0, R = -1;
void shift(int l, int r) {
while (R < r) {
tog(++R);
}
while (L > l) {
tog(--L);
}
while (R > r) {
tog(R--);
}
while (L < l) {
tog(L++);
}
}
long long res = 0;
void dc(int l, int r, int u, int v) {
if (l > r) {
return;
}
int m = (l + r) / 2;
pair<long long, int> best = {-inf, -1};
for (int i = max(u, m); i <= v; ++i) {
shift(m, i);
int dis = min(start - m + i - m, i - start + i - m);
if (dis <= d) {
int cnt = min(d - dis, i - m + 1);
long long x = !cnt ? 0 : qry(cnt);
best = max(best, {x, i});
}
}
res = max(res, best.first);
dc(l, m - 1, u, best.second);
dc(m + 1, r, best.second, v);
}
long long findMaxAttraction(int n, int s, int d, int *a) {
vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return a[i] > a[j];
});
::n = n, ::start = s, ::d = d;
for (int i = 0; i < n; ++i) {
rk[ord[i]] = i;
::a[i] = a[i];
}
dc(max(0, start - d), start, start, n - 1);
return res;
}
