#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll val[100005],ver[100005];
vector<ll>disc;
ll n;
ll find(ll k){
return lower_bound(disc.begin(),disc.end(),k)-disc.begin();
}
struct PSEG{
ll sum[2200005];
int cnt[2200005],lc[2200005],rc[2200005];
ll assign=1;
ll build(ll l, ll r){
if(l==r){
assign++;
}
else{
ll mid=(l+r)>>1;
build(l,mid);
ll le=assign-1;
build(mid+1,r);
ll ri=assign-1;
lc[assign]=le,rc[assign]=ri;
// cout<<l<<" "<<r<<" "<<assign<<" "<<lc[assign]<<" "<<rc[assign]<<'\n';
assign++;
}
if(l==0&&r==n-1)return assign-1;
return 0;
}
ll upd(ll ul, ll l, ll r, ll valsum, ll valcnt, ll id){
if(l==r){
ll cur=assign;assign++;
sum[cur]=sum[id]+valsum;
cnt[cur]=cnt[id]+valcnt;
lc[cur]=0,rc[cur]=0;
}
else{
ll mid=(l+r)>>1;
if(ul<=mid){
upd(ul,l,mid,valsum,valcnt,lc[id]);
ll cur=assign++;
sum[cur]=sum[id]+valsum,cnt[cur]=cnt[id]+valcnt;
lc[cur]=cur-1,rc[cur]=rc[id];
}
else{
upd(ul,mid+1,r,valsum,valcnt,rc[id]);
ll cur=assign;assign++;
sum[cur]=sum[id]+valsum,cnt[cur]=cnt[id]+valcnt;
lc[cur]=lc[id],rc[cur]=cur-1;
}
}
if(l==0&&r==n-1){
return assign-1;
}
return 0;
}
void bs(ll& totsum, ll id1, ll id2, ll l, ll r, ll k){
if(l==r){
totsum+=(min((ll)k,(ll)cnt[id1]-cnt[id2])*val[l]);
// cout<<totsum<<'\n';
return;
}
ll mid=(l+r)>>1;
if(cnt[rc[id1]]-cnt[rc[id2]]>=k){
bs(totsum,rc[id1],rc[id2],mid+1,r,k);
}
else{
totsum+=sum[rc[id1]]-sum[rc[id2]];
bs(totsum,lc[id1],lc[id2],l,mid,k-(cnt[rc[id1]]-cnt[rc[id2]]));
}
}
void clear(){
for(int i=1;i<=2000000;i++){
sum[i]=0,cnt[i]=0,lc[i]=0,rc[i]=0;
}
assign=1;
}
}st;
int starting,day;
ll ans=0;
vector<ll>att;
ll cost(ll from, ll to, ll k){
// cout<<from<<" "<<to<<" "<<k<<'\n';
if(from>to)return -1e18;
if(k<0)return -1e18;
ll extra=to-from;
if(k<=extra)return -1e18;
k-=extra;
ll ans=0;
// cout<<to+1<<' '<<from<<" "<<k<<'\n';
st.bs(ans,ver[to+1],ver[from],0,n-1,k);
return ans;
}
void find_bst(ll l, ll r, ll optl, ll optr){
if(l>r)return;
ll mid=(l+r)>>1;
ll bstid=optl,bst=cost(mid,optl,day-(abs(mid-starting)));
ll kk=day-abs(mid-starting);
for(int i=optl+1;i<=optr;i++){
if(cost(mid,i,kk)>bst){
bst=cost(mid,i,kk),bstid=i;
}
}
ans=max(ans,bst);
find_bst(l,mid-1,optl,bstid),find_bst(mid+1,r,bstid,optr);
}
ll findMaxAttraction(int _n, int start, int d, int attraction[]){
n=_n;
for(int i=0;i<_n;i++){
att.push_back(attraction[i]);
}
for(int i=0;i<_n;i++){
disc.push_back(att[i]);
}
// return 0;
sort(disc.begin(),disc.end());disc.erase(unique(disc.begin(),disc.end()),disc.end());
n=disc.size();
for(int i=0;i<n;i++)val[i]=disc[i];
ver[0]=st.build(0,n-1);
for(int i=0;i<_n;i++){
ver[i+1]=st.upd(find(att[i]),0,n-1,att[i],1,ver[i]);
}
// return 0;
starting=start,day=d;
find_bst(0,start,0,_n-1);
st.clear();
reverse(att.begin(),att.end());
ver[0]=st.build(0,n-1);
starting=_n-starting-1;
for(int i=0;i<_n;i++){
ver[i+1]=st.upd(find(att[i]),0,n-1,att[i],1,ver[i]);
}
find_bst(0,starting,0,_n-1);
return ans;
}
// int main() {
// int n, start, d;
// int attraction[100000];
// int i, n_s;
// n_s = scanf("%d %d %d", &n, &start, &d);
// for (i = 0 ; i < n; ++i) {
// n_s = scanf("%d", &attraction[i]);
// }
// printf("%lld\n", findMaxAttraction(n, start, d, attraction));
// return 0;
// }
