#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
void maxself(long long& x,long long val){
if(x<val)
x=val;
}
int const INF=1000000000;
int const MAX=3200000;
int const NMAX=100005;
int root[NMAX];
long long ans;
int total;
int cnt[MAX],lson[MAX],rson[MAX];
long long sum[MAX];
void update(int nod,int past,int st,int dr,int poz){
if(st==dr){
cnt[nod]=cnt[past]+1;
sum[nod]=sum[past]+poz;
}
else{
int mij=(st+dr)/2;
if(poz<=mij){
lson[nod]=++total;
rson[nod]=rson[past];
update(lson[nod],lson[past],st,mij,poz);
}
else{
lson[nod]=lson[past];
rson[nod]=++total;
update(rson[nod],rson[past],mij+1,dr,poz);
}
cnt[nod]=cnt[lson[nod]]+cnt[rson[nod]];
sum[nod]=sum[lson[nod]]+sum[rson[nod]];
}
}
long long get_sum(int nod1,int nod2,int st,int dr,int k){
if(st==dr)
return 1LL*k*st;
int mij=(st+dr)/2;
int dreapta=cnt[rson[nod1]]-cnt[rson[nod2]];
if(dreapta>=k)
return get_sum(rson[nod1],rson[nod2],mij+1,dr,k);
return sum[rson[nod1]]-sum[rson[nod2]]+get_sum(lson[nod1],lson[nod2],st,mij,k-dreapta);
}
void dei(int l,int r,int optl,int optr,int start,int d){
if(l>r)
return;
int optIndex=0;
long long optAns=-1;
int i;
int mij=(l+r)/2;
for(i=optl;i<=optr;++i){
int drum1=start-mij;
int drum2=i-start;
int drum=((drum1<drum2)?2*drum1+drum2:drum1+2*drum2);
int k=d-drum;
long long rasp=0;
if(k>0)
rasp=get_sum(root[i+1],root[mij],0,INF,min(k,i-mij+1));
if(rasp>optAns){
optAns=rasp;
optIndex=i;
}
}
maxself(ans,optAns);
dei(l,mij-1,optl,optIndex,start,d);
dei(mij+1,r,optIndex,optr,start,d);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]){
int i;
for(i=0;i<n;++i){
root[i+1]=++total;
update(root[i+1],root[i],0,INF,attraction[i]);
}
dei(0,start,start,n-1,start,d);
return ans;
}
