#include"holiday.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=1e5+5;
int N,niz[maxn],D,poc;
priority_queue<int> PQ;
ll suma,res=0;
ll summaxk(int l,int r,int k){
while(PQ.size())
PQ.pop();
ll s=0;
for(int i=l;i<=r;i++){
s+=niz[i];
PQ.push(-niz[i]);
while(PQ.size()>k){
s+=PQ.top();
PQ.pop();
}
}
return s;
}
struct slog{
int l,r,m,poz;
ll v;
int lj,rj;
};
vector<slog> V,novi;
void update(int idx,ll vred,int j){
if(V[idx].v>=vred)
return;
V[idx].v=vred;
V[idx].poz=j;
res=max(res,vred);
}
void split(int idx){
slog a,b,x=V[idx];
a.l=x.l;
a.r=x.m-1;
a.m=(a.l+a.r)/2;
a.lj=x.lj;
a.rj=x.poz;
a.v=0;
a.poz=a.rj;
b.l=x.m+1;
b.r=x.r;
b.m=(b.l+b.r)/2;
b.lj=x.poz;
b.rj=x.rj;
b.v=0;
b.poz=b.rj;
if(a.l<=a.r)
novi.push_back(a);
if(b.l<=b.r)
novi.push_back(b);
}
vector<pair<pair<int,int>,pair<int,int>>> upiti;
void makeq(int idx){
for(int j=V[idx].lj;j<=V[idx].rj;j++){
int d=V[idx].m-j+min(poc-j,V[idx].m-poc);
if(d>=D)
continue;
int k=D-d;
upiti.push_back({{j,V[idx].m},{k,idx}});
}
}
void processq(pair<pair<int,int>,pair<int,int>> x){
int l=x.f.f;
int r=x.f.s;
int k=x.s.f;
int idx=x.s.s;
ll v=summaxk(l,r,k);
update(idx,v,l);
}
void makestep(){
upiti.clear();
for(int i=0;i<V.size();i++){
makeq(i);
}
if(upiti.size()==0){
V.clear();
return;
}
sort(upiti.begin(),upiti.end());
for(auto x:upiti)
processq(x);
novi.clear();
for(int i=0;i<V.size();i++)
split(i);
V.clear();
V=novi;
}
long long int findMaxAttraction(int n, int start, int ddd, int attraction[]) {
N=n;
for(int i=1;i<=N;i++)
niz[i]=attraction[i-1];
D=ddd;
start++;
poc=start;
slog a;
a.l=start;
a.r=N;
a.lj=1;
a.rj=start;
a.m=(a.l+a.r)/2;
a.poz=a.rj;
a.v=0;
V.push_back(a);
while(V.size()){
makestep();
}
return res;
}
