#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
template<class T, class U>
using ordered_set=tree<T, null_type, U, rb_tree_tag, tree_order_statistics_node_update>;
struct DS{
int count;
int sum;
ordered_set<pair<int, int>, greater<pair<int, int>>> st;
void clear(){
// cerr << "clear" << endl;
count=0;
sum=0;
st.clear();
}
DS (){
clear();
}
int size(){
return st.size();
}
void set_count(int new_count){
new_count=max(new_count, 0ll);
while (count<new_count){
if (size()>count) sum+=st.find_by_order(count)->first;
++count;
}
while (count>new_count){
--count;
if (size()>count) sum-=st.find_by_order(count)->first;
}
}
void insert(pair<int, int> x){
// cerr << "insert " << x.second << endl;
int id=st.order_of_key(x);
if (id<count){
sum+=x.first;
st.insert(x);
if (size()>count) sum-=st.find_by_order(count)->first;
}else st.insert(x);
}
void erase(pair<int, int> x){
// cerr << "erase " << x.second << endl;
int id=st.order_of_key(x);
if (id<count){
sum-=x.first;
st.erase(x);
if (size()>=count) sum+=st.find_by_order(count-1)->first;
}else st.erase(x);
}
} st;
const int N=1e5;
int a[N], n, start, d, ans;
void dnc(int l, int r, int optl, int optr){
if (l>r) return;
int mid=(l+r)>>1;
for (int i=mid; i<r; ++i) st.insert({a[i], i});
st.set_count(d-(start-mid)-(optl-mid));
int optmid=optl, optval=st.sum;
for (int i=optl+1; i<=optr; ++i){
st.set_count(d-(start-mid)-(i-mid));
st.insert({a[i], i});
if (optval<st.sum){
optmid=i;
optval=st.sum;
}
}
ans=max(ans, optval);
for (int i=mid; i<r; ++i) st.erase({a[i], i});
for (int i=optl+1; i<=optr; ++i) st.erase({a[i], i});
if (mid>0){
// r -> optl -> mid - 1 -> optl
for (int i=mid-1; i<r; ++i) st.insert({a[i], i});
dnc(l, mid-1, optl, optmid);
for (int i=mid-1; i<r; ++i) st.erase({a[i], i});
}
if (mid+1<n){
// r -> optl -> r -> optmid
for (int i=optl+1; i<=optmid; ++i) st.insert({a[i], i});
// r -> optmid
dnc(mid+1, r, optmid, optr);
for (int i=optl+1; i<=optmid; ++i) st.erase({a[i], i});
}
}
void solve(){
for (int l=start; l>=0; --l){
st.set_count(d-(start-l));
st.insert({a[l], l});
ans=max(ans, st.sum);
}
st.clear();
st.insert({a[start], start});
dnc(0, start, start, n-1);
st.clear();
}
int findMaxAttraction(int32_t _n, int32_t _start, int32_t _d, int32_t _a[]) {
n=_n; start=_start; d=_d;
for (int i=0; i<n; ++i) a[i]=_a[i];
solve();
reverse(a, a+n);
start=n-start-1;
solve();
return ans;
}
