#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define ins insert
#define pb push_back
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
const int mx = 100005;
const int DIFF = 30;
int n;
int S;
int d;
vl w;
void reversedir(){
S = n-1-S;
reverse(all(w));
}
//////TOPK SECTION BEGINS
int k;
set<pi> indices;
void CLEAR(){
indices.clear();
}
void INSERT(int ind){
indices.ins(mp(w[ind], ind));
}
void ERASE(int ind){
indices.erase(mp(w[ind], ind));
}
ll getsum(){
auto it = prev(indices.end());
ll ans = 0;
int num = 0;
while(num < k){
ans+=it->f;
num++;
if(it == indices.begin()) break;
it = prev(it);
}
return ans;
}
//TOPK SECTION ENDS
ll solvefixedlengthdirection(int len){ //going left to right
CLEAR();
k = len;
int days = d-len;
int lastr = -5; //last r that is still in topk or couldtake
ll ans = 0;
for(int i = S; i >= 0; i--){
int curr = (days-(S-i))+i;
ckmin(curr, n-1);
if(curr-i+1 < len) continue;
if(lastr == -5){
for(int j = i; j <= curr; j++){
INSERT(j);
}
lastr = curr;
}
else{
while(lastr > curr){
ERASE(lastr);
lastr--;
}
INSERT(i);
}
ckmax(ans, getsum());
}
return ans;
}
ll solvefixedlength(int len){
if(len <= 0 || len > n) return 0;
ll ans = 0;
ckmax(ans, solvefixedlengthdirection(len));
reversedir();
ckmax(ans, solvefixedlengthdirection(len));
return ans;
}
ll solverightonly(int L, int days){ //only move right from L
set<pi> taken;
ll ans = 0;
ll cursum = 0;
for(int i = L; i < n; i++){
int num = days-(i-L);
if(num <= 0) break;
if(sz(taken) > num){
assert(num == sz(taken)-1);
pi lowest = *(taken.begin());
taken.erase(lowest);
cursum-=lowest.f;
}
pi couldtake = mp(w[i], i);
if(sz(taken) < num){
taken.ins(couldtake);
cursum+=couldtake.f;
}
else{
pi lowest = *(taken.begin());
if(lowest.f < couldtake.f){
taken.erase(lowest);
cursum-=lowest.f;
taken.ins(couldtake);
cursum+=couldtake.f;
}
}
ckmax(ans, cursum);
}
return ans;
}
ll solve(){ //go left, then right
if(d == 0) return 0;
clock_t c = clock();
ll ans = 0;
ckmax(ans, solverightonly(S, d));
reversedir();
ckmax(ans, solverightonly(S, d));
//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
int lo = 1;
int hi = min(n, d+1);
while(hi-lo > 3){
int mid1 = (2*lo+hi)/3;
int mid2 = (2*hi+lo)/3;
ll ans1 = solvefixedlength(mid1);
//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
ll ans2 = solvefixedlength(mid2);
//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
if(ans1 == 0){
lo = mid1;
}
else if(ans2 == 0){
hi = mid2;
}
else if(ans1 > ans2){
hi = mid2;
}
else{
lo = mid1;
}
}
//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
lo = (lo+hi)/2;
for(int i = 0; i <= DIFF; i++){
ckmax(ans, solvefixedlength(lo-i));
ckmax(ans, solvefixedlength(lo+i));
}
//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
return ans;
}
ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
cout << fixed << setprecision(10);
n = _n;
S = start;
d = _d;
for(int i = 0; i < n; i++){
w.pb(attraction[i]);
}
return solve();
}
