#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 1e5+5;
int n, start, d, cnt[MXN<<2], ord[MXN], a[MXN], pos[MXN];
ll sum[MXN<<2];
void upd(int p, bool ac, int l=0, int r=n+1, int id=1) {
if(r-l == 1) {
cnt[id] = ac;
sum[id] = ac ? a[ord[l]] : 0;
return;
}
p<mid ? upd(p, ac, l, mid, lc) : upd(p, ac, mid, r, rc);
cnt[id] = cnt[lc] + cnt[rc];
sum[id] = sum[lc] + sum[rc];
}
int cnt_;
ll sum_;
void get_(int l=0, int r=n+1, int id=1) {
if(r-l == 1) return;
if(cnt[lc]<=cnt_) {
sum_ += sum[lc];
cnt_ -= cnt[lc];
get_(mid, r, rc);
}
else get_(l, mid, lc);
}
inline ll get(int k) {
cnt_ = k;
sum_ = 0;
get_();
return sum_;
}
int L=1, R=0;
inline void adjust(int l, int r) {
while(R<r) upd(pos[++R], 1);
while(L>l) upd(pos[--L], 1);
while(R>r) upd(pos[R--], 0);
while(L<l) upd(pos[L++], 0);
}
ll ans;
void dnql(int l, int r, int opl, int opr) {
if(l>r) return;
ll cur = -1, tmp;
int op = opl;
for(int i=max(mid, opl); i<=opr && start+i-2*mid<=d; i++) {
adjust(mid, i);
tmp = get(d - (start+i-2*mid));
if(tmp>cur) {
cur = tmp;
op = i;
}
}
ans = max(ans, cur);
dnql(l, mid-1, opl, op);
dnql(mid+1, r, op, opr);
}
void dnqr(int l, int r, int opl, int opr) {
if(l>r) return;
ll cur = -1, tmp;
int op = opl;
for(int i=min(mid,opr); i>=opl && 2*mid-start-i<=d; i--) {
adjust(i, mid);
tmp = get(d - (2*mid-start-i));
if(tmp>cur) {
cur = tmp;
op = i;
}
}
ans = max(ans, cur);
dnqr(l, mid-1, opl, op);
dnqr(mid+1, r, op, opr);
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
::n = n;
::start = start;
::d = d;
for(int i=0; i<n; i++) a[i] = attraction[i], ord[i] = i;
sort(ord, ord+n, [&](int i, int j) {
return a[i] > a[j];
});
for(int i=0; i<n; i++) pos[ord[i]] = i;
dnql(max(0, start-d), start, 0, n-1);
dnqr(start, min(n-1, start+d), 0, n-1);
return ans;
}
