#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
typedef long long ll;
#define maxn 100005
int n,s,d,a[maxn],cantake,lptr,rptr;
ll pfx[maxn],ans,sm;
multiset<ll> in,out;
void fix(){
while(in.size()>cantake){
auto it=in.begin();
sm-=*it;
out.insert(*it);
in.erase(it);
}
while(in.size()<cantake&&!out.empty()){
auto it=--out.end();
sm+=*it;
in.insert(*it);
out.erase(it);
}
}
void add(int x){
sm+=x;
in.insert(x);
fix();
}
void rem(int x){
if(out.find(x)!=out.end()){
out.erase(out.find(x));
}
else{
in.erase(in.find(x));
sm-=x;
fix();
}
}
void dnc(int l,int r,int optl,int optr){
if(l>r)return;
int m=(l+r)>>1;
while(lptr<m)rem(a[lptr++]);
while(m<lptr)add(a[--lptr]);
while(rptr<optl-1)add(a[++rptr]);
while(optl-1<rptr)rem(a[rptr--]);
ll mx=0,best=0;
for(int i=optl;i<=optr;++i){
add(a[i]);
cantake=max(d-(s-m+i-m),0);
fix();
if(sm>=mx)best=i,mx=sm;
}
rptr=optr;
ans=max(ans,mx);
dnc(l,m-1,optl,best);
dnc(m+1,r,best,optr);
}
void solve(){
in.clear();out.clear();
sm=cantake=0;
lptr=1,rptr=s;
for(int i=s;i>=1;--i){
add(a[i]);
cantake=max(d-(s-i),0);
fix();
ans=max(ans,sm);
}
dnc(1,s-1,s,n);
}
ll findMaxAttraction(int _n,int _s,int _d,int _a[]){
n=_n,s=_s+1,d=_d;
for(int i=1;i<=n;++i)a[i]=_a[i-1];
solve();
for(int i=1;i<=n/2;++i)swap(a[i],a[n-i+1]);
s=n-s+1;
solve();
return ans;
}
