#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(){
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){
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){
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 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();
for (int i=0; i<start; ++i) st.insert({a[i], i});
for (int l=0, r=start-1; l<=start; ++l){
while (r+1<n){
int old_val=st.sum;
st.insert({a[r+1], r+1});
st.set_count(d-(start-l)-(r+1-l));
int new_val=st.sum;
if (new_val<old_val){
st.erase({a[r+1], r+1});
st.set_count(d-(start-l)-(r-l));
break;
}
++r;
}
ans=max(ans, st.sum);
st.erase({a[l], l});
}
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();
start=n-start-1;
reverse(a, a+n);
solve();
return ans;
}
