#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
struct Node {
long long sum = 0;
int cnt = 0;
int ln = 0, rn = 0;
};
int n;
vector<int> dom;
vector<Node> nodes;
SegmentTree(int n, vector<int> dom) : n(n), dom(dom), nodes(1) {
nodes.reserve(n * (32 - __builtin_clz(n)));
}
void add(int i, int base, int &aug, int l, int r) {
aug = nodes.size();
nodes.push_back(nodes[base]);
nodes[aug].cnt++;
nodes[aug].sum += dom[i];
if (l + 1 < r) {
int m = (l + r) >> 1;
if (i < m) add(i, nodes[base].ln, nodes[aug].ln, l, m);
else add(i, nodes[base].rn, nodes[aug].rn, m, r);
}
}
long long sum(int k, int idxl, int idxr, int l, int r) {
if (l + 1 == r) {
return 1LL * k * dom[l];
} else {
int m = (l + r) >> 1;
int right_cnt = nodes[nodes[idxr].rn].cnt - nodes[nodes[idxl].rn].cnt;
if (k >= right_cnt) {
return sum(k - right_cnt, nodes[idxl].ln, nodes[idxr].ln, l, m) + nodes[nodes[idxr].rn].sum - nodes[nodes[idxl].rn].sum;
} else {
return sum(k, nodes[idxl].rn, nodes[idxr].rn, m, r);
}
}
}
void add(int i, int base, int &aug) { add(i, base, aug, 0, n); }
long long sum(int k, int idxl, int idxr) { return sum(k, idxl, idxr, 0, n); }
};
long long findMaxAttraction(int n, int s, int d, int attraction[]) {
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = attraction[i];
vector<int> dom = a;
sort(dom.begin(), dom.end());
dom.resize(unique(dom.begin(), dom.end()) - dom.begin());
int C = dom.size();
for (int &x : a) x = lower_bound(dom.begin(), dom.end(), x) - dom.begin();
SegmentTree st(n, dom);
vector<int> root(n + 1);
root[0] = 0;
for (int i = 0; i < n; i++) {
st.add(a[i], root[i], root[i + 1]);
}
long long ans = 0;
for (int l = 0; l <= s; l++) {
for (int r = s + 1; r <= n; r++) {
int distance_to_walk = min(s - l, r - s - 1) + r - l - 1;
int playtime = d - distance_to_walk;
if (playtime > 0) {
ans = max(ans, st.sum(playtime, root[l], root[r]));
}
}
}
return ans;
}
//int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
//
// int n, s, d;
// cin >> n >> s >> d;
// int a[n];
// for (int i = 0; i < n; i++) {
// cin >> a[i];
// }
//
// cout << findMaxAttraction(n, s, d, a) << '\n';
//}
