#include <bits/stdc++.h>
#include "holiday.h"
#define em emplace
using namespace std;
using ll = long long;
const int MX = 1e5 + 5;
int N, S, D;
ll H[MX], A;
struct myset {
multiset<ll> S1, S2;
ll V; int s, e;
void init() {
s=0; e=-1; V=0;
S1.clear(); S2.clear();
}
void ins(int i) {
if (S1.empty()||*S1.rbegin()<H[i]) S2.em(H[i]), V+=H[i];
else S1.em(H[i]);
}
void er(int i) {
if (S1.find(H[i])!=S1.end()) S1.erase(S1.find(H[i]));
else if (S2.find(H[i])!=S2.end()) S2.erase(S2.find(H[i])), V-=H[i];
else assert(false);
}
void res(int ss, int ee) {
for (int i=s-1; i>=ss; i--) ins(i);
for (int i=e+1; i<=ee; i++) ins(i);
for (int i=s; i<ss; i++) er(i);
for (int i=e; i>ee; i--) er(i);
s=ss; e=ee;
}
ll get(int c) {
if (c<=0) return 0;
while (S2.size()<c&&S1.size()>0) V+=*S1.rbegin(), S2.em(*S1.rbegin()), S1.erase(--S1.end());
while (S2.size()>c) V-=*S2.begin(), S1.em(*S2.begin()), S2.erase(S2.begin());
return V;
}
}MS;
void sol(int s, int e, int ss, int ee) {
if (s>e||ss>ee) return ;
int m=(s+e)/2, mi=ss; ll mx=0;
for (int i=ss; i<=ee; i++) {
MS.res(m, i);
ll r=MS.get(D-(S+i-2*m));
if (r>mx) mx=r, mi=i;
}
A=max(A, mx);
if (s==e) return ;
sol(s, m-1, ss, mi); sol(m+1, e, mi, ee);
}
ll findMaxAttraction(int n, int s, int d, int h[]) {
N=n, S=s, D=d;
for (int i=0; i<N; i++) H[i]=h[i];
MS.init();
sol(0, S, S+1, N-1);
reverse(H, H+N); S=N-1-S; MS.init();
sol(0, S, S+1, N-1);
return A;
}
