#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int n,s,d,a[100001],idx[100001],pos[100001];
pair <long long, int> p[250001][2],st[400001];
void update(int node, int l, int r, int i){
if (l>i||r<i||l>r)
return;
if (l==r){
st[node].second^=1;
st[node].first=st[node].second*a[i];
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,i);
update(node<<1|1,mid+1,r,i);
st[node]={st[node<<1].first+st[node<<1|1].first,st[node<<1].second+st[node<<1|1].second};
}
long long get(int node, int l, int r, int x){
if (st[node].second<=x)
return st[node].first;
int mid=(l+r)>>1;
return (st[node<<1|1].second<x?get(node<<1,l,mid,x-st[node<<1|1].second)+st[node<<1|1].first:get(node<<1|1,mid+1,r,x));
}
void dnc(int l, int r, int optl, int optr, int idx){
if (l>r||optl>optr)
return;
int mid=(l+r)>>1;
for (int i=optl;i<=min(s+mid/(idx+1),optr);i++){
update(1,0,n-1,pos[i]);
p[mid][idx]=max(p[mid][idx],make_pair(get(1,0,n-1,mid-(i-s)*(idx+1)),-i));
}
int opt=-p[mid][idx].second;
for (int i=opt;i<=min(s+mid/(idx+1),optr);i++)
update(1,0,n-1,pos[i]);
dnc(mid+1,r,opt,optr,idx);
for (int i=optl;i<opt;i++)
update(1,0,n-1,pos[i]);
dnc(l,mid-1,optl,opt,idx);
}
long long solve(){
for (int i=0;i<n;i++)
idx[i]=i;
for (int i=0;i<=d;i++)
p[i][0]=p[i][1]={0,-1e9};
sort(idx,idx+n,[](int i, int j){return make_pair(a[i],i)<make_pair(a[j],j);});
sort(a,a+n);
for (int i=0;i<n;i++)
pos[idx[i]]=i;
if (s<n-1){
s++;
dnc(0,d,s,n-1,0);
s--;
}
reverse(pos,pos+n);
s=n-1-s;
dnc(0,d,s,n-1,1);
for (int i=0;i<n*4;i++)
assert(!st[i].second);
long long res=0;
for (int i=0;i<=d;i++)
res=max(res,p[i][0].first+p[max(d-i-1,0)][1].first);
return res;
}
long long findMaxAttraction(int N, int start, int D, int attraction[]){
n=N;
s=start;
d=D;
for (int i=0;i<n;i++)
a[i]=attraction[i];
long long res=solve();
for (int i=0;i<n;i++)
a[i]=attraction[n-i-1];
s=n-start-1;
return max(res,solve());
}
