#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=100010;
const int maxm=3200010;
int n,s,d,i,l,r,m,x,p1,p2,tot;
int a[maxn],rt[maxn]; LL ans,sum[maxm];
int ls[maxm],rs[maxm],cnt[maxm];
void solve(int ll,int lr,int rl,int rr){
if(ll>lr||rl>rr) return; int lm=(ll+lr)>>1;
if(d<(s-lm)<<1){solve(lm+1,lr,rl,rr);return;}
int rk=min(rr,rl+d-((s-lm)<<1)),rm=rl; LL mx=0,nw;
for(i=rl;i<=rk;++i){
l=0; r=1e9; x=d-(i-lm)-(s-lm);
nw=0; p1=rt[i]; p2=rt[lm-1];
if(cnt[p1]-cnt[p2]<=x) nw=sum[p1]-sum[p2];
else{
while(l<r){
m=(l+r)>>1;
if(cnt[rs[p1]]-cnt[rs[p2]]<=x){
x-=cnt[rs[p1]]-cnt[rs[p2]];
nw+=sum[rs[p1]]-sum[rs[p2]];
r=m; p1=ls[p1]; p2=ls[p2];
}
else l=m+1,p1=rs[p1],p2=rs[p2];
}
nw+=1LL*l*min(x,cnt[p1]-cnt[p2]);
}
if(nw>mx) mx=nw,rm=i;
}
if(ans<mx) ans=mx;
solve(ll,lm-1,rl,rm);
solve(lm+1,lr,rm,rr);
}
void build(){
l=0; r=1e9; x=a[i]; rt[i]=++tot; p1=rt[i-1];
ls[tot]=ls[p1]; rs[tot]=rs[p1];
sum[tot]=sum[p1]+x; cnt[tot]=cnt[p1]+1;
while(l<r){
m=(l+r)>>1;
if(x<=m) p1=ls[tot],ls[tot]=tot+1,r=m;
else p1=rs[tot],rs[tot]=tot+1,l=m+1;
rs[++tot]=rs[p1]; ls[tot]=ls[p1];
sum[tot]=sum[p1]+x; cnt[tot]=cnt[p1]+1;
}
}
long long findMaxAttraction(int n,int s,int d,int a[]){
++s; for(i=n;i;--i) a[i]=a[i-1]; for(i=1;i<=n;++i) build();
solve(max(1,s-(d<<1)),s,s,min(n,s+d)); reverse(a+1,a+n+1);
s=n-s+1; tot=0; for(i=1;i<=n;++i) build();
solve(max(1,s-(d<<1)),s,s,min(n,s+d)); return ans;
}
