#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,lg=18;
const ll INF=1e18;
void chmx(ll &x,ll y){x=max(x,y);}
int n,S,D,a[N];
int root[N],nc,lc[N*lg],rc[N*lg],num[N*lg];ll sum[N*lg];
void Update(int &c,int c1,int ss,int se,int qind,int x){
c=++nc;lc[c]=lc[c1],rc[c]=rc[c1],num[c]=num[c1],sum[c]=sum[c1];
if(ss==se){num[c]=1,sum[c]=x;return;}
int mid=ss+se>>1;
if(qind<=mid) Update(lc[c],lc[c1],ss,mid,qind,x);
else Update(rc[c],rc[c1],mid+1,se,qind,x);
num[c]=num[lc[c]]+num[rc[c]];
sum[c]=sum[lc[c]]+sum[rc[c]];
}
ll Get(int c,int ss,int se,int qs,int qe){
if(qs>qe||qe<ss||se<qs)return 0;
if(qs<=ss&&se<=qe)return sum[c];
int mid=ss+se>>1;return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
}
int Walk(int cL,int cR,int ss,int se,int k){
if(ss==se)return ss;
int mid=ss+se>>1;
if(num[lc[cR]]-num[lc[cL]]>=k)return Walk(lc[cL],lc[cR],ss,mid,k);
return Walk(rc[cL],rc[cR],mid+1,se,k-(num[lc[cR]]-num[lc[cL]]));
}
void Clear(){
for(int i=0;i<=n;i++)root[i]=0;
for(int i=0;i<=nc;i++)lc[i]=rc[i]=num[i]=sum[i]=0;
nc=0;
}
ll Cost(int l,int r,int k){
k=min(k,r-l+1);
int ind=Walk(root[l-1],root[r],0,n,k);
return Get(root[r],0,n,0,ind)-Get(root[l-1],0,n,0,ind);
}
ll Solve(int ss,int se,int lo,int up){
if(ss>se)return -INF;
int mid=ss+se>>1,opt=0;
ll res=-INF;
for(int i=lo;i<=min(up,mid);i++){
ll x=Cost(i,mid,D-(mid-S+mid-i));
if(x>=res){res=x;opt=i;}
}
chmx(res,Solve(ss,mid-1,lo,opt));
chmx(res,Solve(mid+1,se,opt,up));
return res;
}
ll Calc(){
ll res=-INF;
int ind1[n+10]={0};iota(ind1+1,ind1+n+1,1);
sort(ind1+1,ind1+n+1,[&](int i,int j){return a[i]>a[j];});
int ind[n+10];for(int i=1;i<=n;i++)ind[ind1[i]]=i;
for(int i=1;i<=n;i++) Update(root[i],root[i-1],0,n,ind[i],a[i]);
chmx(res,Solve(S,n,1,S));
for(int i=S;i<=n;i++)chmx(res,Cost(S,i,D-(i-S)));
return res;
}
long long int findMaxAttraction(int n1, int start, int D1, int attraction[]){
n=n1,D=D1;
for(int i=1;i<=n;i++) a[i]=attraction[i-1];
S=start+1;
ll res=Calc();
reverse(a+1,a+n+1);
Clear();
S=n+1-S;
chmx(res,Calc());
return res;
}
