#include<bits/stdc++.h>
#include"holiday.h"
#define LL long long
using namespace std;
void read(int &x){
x=0;char ch=getchar();int f=1;
while((ch<'0'||ch>'9')&&ch!=45)ch=getchar();
if(ch==45)ch=getchar(),f=-1;
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
x*=f;
}
template<typename T1,typename T2>void cmax(T1 &x,const T2 &y){if(y>x)x=y;}
template<typename T1,typename T2>void cmin(T1 &x,const T2 &y){if(y<x)x=y;}
const int N=3e5+10;
int m;
int b[N];
LL ans[N];
struct KthTree{
multiset<int> s1,s2;
LL sum;
void clear(){
sum=0;s1.clear(),s2.clear();
}
void insert(int x){
sum+=x;
s1.insert(x);
}
LL qry(int k){
while(s1.size()<k&&!s2.empty()){
sum+=*s2.rbegin();
s1.insert(*s2.rbegin());
s2.erase(s2.find(*s2.rbegin()));
}
while(!s1.empty()&&(int)s1.size()>k){
sum-=*s1.begin();
s2.insert(*s1.begin());
s1.erase(s1.begin());
}
return sum;
}
}T;
vector<LL> solve(vector<int> a,int d,int c,int ex=0){
memset(ans,0,sizeof(ans));
queue<tuple<int,int,int,int>> q1,q2;
q2.push(make_tuple(1,d,1,a.size()-1));
while(!q2.empty()){
swap(q1,q2);T.clear();
int p=-1;
while(!q1.empty()){
auto [l1,r1,l2,r2]=q1.front();q1.pop();
LL mid=l1+r1>>1,val=-1,pos=0;
auto upd=[&](int x){
LL res=T.qry(mid-c*(x+ex));
if(res>val)val=res,pos=x;
};
upd(p);
while(p+1<=r2){
T.insert(a[++p]);
upd(p);
}
ans[mid]=val;
if(mid-1>=l1)q2.push(make_tuple(l1,mid-1,l2,pos));
if(r1>=mid+1)q2.push(make_tuple(mid+1,r1,pos,r2));
}
}
return vector<LL>(ans,ans+d+1);
}
LL findMaxAttraction(int n,int start,int d,int w[]){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//freopen(".in","w",stdout);
int i;
LL ans=0;
// read(n),read(start),read(d);
vector<int> a;
a.resize(n);
for(i=0;i<n;i++)b[i+1]=a[i]=w[i];
sort(b+1,b+1+n);m=unique(b+1,b+n+1)-b-1;
for(int o=0;o<=1;o++){
auto f=solve(vector<int>(a.begin()+start,a.end()),d,o?1:2);
vector<int> w(a.begin(),a.begin()+start);
reverse(w.begin(),w.end());
auto g=solve(w,d,o?2:1,1);
for(i=0;i<=d;i++)cmax(ans,f[i]+g[d-i]);
}
return ans;
}
