#include <bits/stdc++.h>
using namespace std;
const int RES = 20e5;
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(RES);
}
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(C, 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;
function<void(int, int, int, int)> compute = [&](int l, int r, int optl, int optr) {
if (l > r) return;
int m = (l + r) >> 1;
long long f = 0;
int opt = optl;
for (int i = optl; i <= optr; i++) {
int distance_to_walk = min(s - i, m - 1 - s) + m - 1 - i;
int playtime = min(m - i, max(0, d - distance_to_walk));
long long get = st.sum(playtime, root[i], root[m]);
if (get > f) {
f = get;
opt = i;
}
}
ans = max(ans, f);
compute(l, m - 1, optl, opt);
compute(m + 1, r, opt, optr);
};
compute(s + 1, n, 0, s);
return ans;
}
//int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// freopen("inp.inp", "r", stdin);
// freopen("out.out", "w", stdout);
//
// 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';
//}
