#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
#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 = 20;
int n;
int S;
int d;
vl w;
void reversedir(){
S = n-1-S;
reverse(all(w));
}
ll solvefixedlengthdirection(int len){ //going left to right
int days = d-len;
set<pair<ll, int>> taken;
set<pair<ll, int>> couldtake;
int lastr = -5; //last r that is still in taken or couldtake
int lastl = -5; //last l that was added
ll ans = 0;
ll cursum = 0; //sum of everything inside of taken
for(int i = S; i >= 0; i--){
int curr = (days-(S-i))+i;
ckmin(curr, n-1);
/*if(len == 3){
cout << i << " " << curr << "\n";
}*/
if(curr-i+1 < len) continue; //should continue forever at the end, continue until relevant in the beginning
if(lastr == -5){ //first interval
for(int j = i; j <= curr; j++){
couldtake.ins(mp(w[j], j));
}
lastl = i;
lastr = curr;
while(sz(taken) < len){
assert(sz(couldtake) > 0);
pair<ll, int> good = *(prev(couldtake.end()));
//put the best value into taken
couldtake.erase(good);
taken.ins(good);
cursum+=good.f;
}
}
else{
while(lastr > curr){
pair<ll, int> bad = mp(w[lastr], lastr);
if(couldtake.find(bad) != couldtake.end()){
couldtake.erase(bad);
}
if(taken.find(bad) != taken.end()){
taken.erase(bad);
cursum-=bad.f;
}
lastr--;
}
while(lastl > i){
lastl--;
couldtake.ins(mp(w[lastl], lastl));
}
while(sz(taken) < len){
assert(sz(couldtake) > 0);
pair<ll, int> good = *(prev(couldtake.end()));
//put the best value into taken
couldtake.erase(good);
taken.ins(good);
cursum+=good.f;
}
while(sz(couldtake)){
pair<ll, int> best = *(prev(couldtake.end()));
pair<ll, int> worst = *(taken.begin());
if(best.f > worst.f){
taken.erase(worst);
cursum-=worst.f;
taken.ins(best);
cursum+=best.f;
couldtake.erase(best);
couldtake.ins(worst);
}
else break;
}
}
ckmax(ans, cursum);
/*if(len == 3){
cout << "taken: ";
for(auto u: taken){
cout << u.f << " ";
}
cout << "\n";
cout << "couldtake: ";
for(auto u: couldtake){
cout << u.f << " ";
}
cout << "\n";
}*/
}
/*if(len == 3){
cout << S << "\n";
for(auto u: w){
cout << u << " ";
}
cout << "\n";
cout << ans << "\n";
}*/
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<pair<ll, int>> 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);
pair<ll, int> lowest = *(taken.begin());
taken.erase(lowest);
cursum-=lowest.f;
}
pair<ll, int> couldtake = mp(w[i], i);
if(sz(taken) < num){
taken.ins(couldtake);
cursum+=couldtake.f;
}
else{
pair<ll, int> 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;
ll ans = 0;
ckmax(ans, solverightonly(S, d));
reversedir();
ckmax(ans, solverightonly(S, d));
int lo = 1;
int hi = min(n, d+1);
while(hi-lo > 10){
int mid1 = (2*lo+hi)/3;
int mid2 = (2*hi+lo)/3;
ll ans1 = solvefixedlength(mid1);
ll ans2 = solvefixedlength(mid2);
if(ans1 == 0){
lo = mid1;
}
else if(ans2 == 0){
hi = mid2;
}
else if(ans1 > ans2){
hi = mid2;
}
else{
lo = mid1;
}
}
lo = (lo+hi)/2;
for(int i = 0; i <= DIFF; i++){
ckmax(ans, solvefixedlength(lo-i));
ckmax(ans, solvefixedlength(lo+i));
}
return ans;
}
ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
n = _n;
S = start;
d = _d;
for(int i = 0; i < n; i++){
w.pb(attraction[i]);
}
return solve();
}
