//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include"holiday.h"
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
using lint = 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 lint MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50,Q = 2e5+50;
vector<lint> a(N),ans(N);
int M;
int L,R;
multiset<int> used,noused;
lint 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]);
}
}
lint 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;
lint 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));
take = min(take,i-m+1);
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);
}
lint findMaxAttraction(int n, int start, int d, int attraction[]) {
for (int i=0;i<n;i++) a[i+1] = attraction[i];
start++;
D = d;
M = start;
ins(M);
L = R = M;
dnc(1,start,start,n);
return *max_element(ans.begin()+1,ans.begin()+start+1);
}
