//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include"holiday.h"
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50,Q = 2e5+50;
vector<int> a(N),ans(N);
int M;
int L,R;
multiset<int> used,noused;
int usum,nsum;
void del(int p) {
if (!noused.empty() && *noused.rbegin() >= a[p]) {
nsum-=a[p];
noused.erase(noused.find(a[p]));
}
else {
usum-=a[p];
used.erase(used.find(a[p]));
}
}
void ins(int p) {
if (used.empty() || a[p] >= *used.begin()) {
usum+=a[p];
used.insert(a[p]);
}
else {
nsum+=a[p];
noused.insert(a[p]);
}
}
int ask(int x) {
while (used.size() < x && !noused.empty()) {
used.insert(*noused.rbegin());
usum+=*noused.rbegin();
nsum-=*noused.rbegin();
noused.erase(prev(noused.end()));
}
while (used.size() > x) {
noused.insert(*used.begin());
nsum+=*used.begin();
usum-=*used.begin();
used.erase(used.begin());
}
return usum;
}
void fix(int l,int r) {
while (L < l) del(L++);
while (R > r) del(R--);
while (L > l) ins(--L);
while (R < r) ins(++R);
}
int D;
void dnc(int l,int r,int optl,int optr) {
if (l > r) return;
int m = (l+r) >> 1;
int best = 0,opt = optl;
for (int i=optl;i<=optr;i++) {
fix(m,i);
int take = D-min(2*(M-L)+(R-M),2*(R-M)+(M-L));
if (take >= 0 && ask(take) > best) {
best = ask(take);
opt = i;
}
}
ans[m] = best;
dnc(l,m-1,optl,opt),dnc(m+1,r,opt,optr);
}
int findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
for (int i=0;i<n;i++) a[i+1] = attraction[i];
D = d;
M = start+1;
ins(M);
L = R = M;
dnc(1,start+1,start+1,n);
return *max_element(ans.begin()+1,ans.end());
}
