#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct SegTree {
struct Node {
int cnt=0;
ll val=0;
};
vector<Node> tree;
SegTree(int n) {
tree.assign(4*n, {});
}
void query(int p, int l, int r, int i, int x) {
if (l>i || r<i) return;
if (l==r) {
tree[p].cnt = 1;
tree[p].val = x;
return;
}
int m = (l+r)/2;
query(2*p, l, m, i, x);
query(2*p+1, m+1, r, i, x);
tree[p].cnt = tree[2*p].cnt + tree[2*p+1].cnt;
tree[p].val = tree[2*p].val + tree[2*p+1].val;
}
ll rsq(int p, int l, int r, int i, int j) {
if (l>j || r<i) return 0;
if (i<=l && r<=j) return tree[p].val;
int m = (l+r)/2;
return rsq(2*p, l, m, i, j) + rsq(2*p+1, m+1, r, i, j);
}
int kth(int p, int l, int r, int k) {
if (l==r) return l;
int m = (l+r)/2;
if (tree[2*p].cnt >= k) {
return kth(2*p, l, m, k);
}
else {
return kth(2*p+1, m+1, r, k-tree[2*p].cnt);
}
}
};
int s, d;
ll findMaxAttraction(int n, int S, int D, int A[]) {
if (D==0) return 0;
s = S;
d = D;
vector<int> a(n);
for (int i=0; i<n; i++) {
a[i] = A[i];
}
vector<pii> b(n);
for (int i=0; i<n; i++) {
b[i] = {a[i], i};
}
sort(b.begin(), b.end(), greater<pii>());
map<int, int> mp;
for (int i=0; i<n; i++) {
mp[b[i].second] = i;
}
SegTree st(n);
ll ans=0;
for (int i=0; i<n; i++) {
int t = d-i;
st.query(1, 0, n-1, mp[i], a[i]);
int j = st.kth(1, 0, n-1, t);
ans = max(ans, st.rsq(1, 0, n-1, 0, j));
}
return ans;
}
