#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
int n, start, days;
int arr[100005];
int opt[100005];
long long ans = 0;
multiset<int> take;
multiset<int, greater<int> > notake;
long long value = 0;
int canTake;
void include(int pos){
if(pos > start) canTake--;
else if(pos < start) canTake -= 2;
take.insert(arr[pos]);
value += arr[pos];
while((int) take.size() > max(canTake,0)){
multiset<int>::iterator it = take.begin();
value -= *it;
notake.insert(*it);
take.erase(it);
}
//cout << "Include " << pos << ": " << value << " " << canTake << " " << "\n";
}
void exclude(int pos){
if(pos > start) canTake++;
else if(pos < start) canTake += 2;
if(take.find(arr[pos]) != take.end()){
take.erase(take.find(arr[pos]));
value -= arr[pos];
}
else notake.erase(notake.find(arr[pos]));
while((int) take.size() < canTake){
if(notake.empty()) break;
multiset<int, greater<int> >::iterator it = notake.begin();
value += *it;
take.insert(*it);
notake.erase(*it);
}
//cout << "Exclude " << pos << ": " << value << " " << canTake << " " << "\n";
}
void reset(){
take.clear();
notake.clear();
value = 0;
canTake = days;
include(start);
}
void solve(){
fill(opt,opt+(n+1),-1);
opt[0] = start;
for(int bit = (1<<17);bit > 0;bit >>= 1){
if(bit > start) continue;
reset();
for(int i = bit;i < start;i++){
include(i);
}
int R = start + 1; ///next value not taken
for(int L = bit;L <= start;L += 2 * bit){
//cout << L << "\n";
int endPoint;
if(L + bit <= start) endPoint = opt[L + bit];
else endPoint = n;
long long best = value;
long long bestR = opt[L - bit];
while(R <= endPoint){
include(R);
if(best < value){
best = value;
bestR = R;
}
R++;
}
opt[L] = bestR;
//cout << L << " " << opt[L] << " " << best << "\n";
ans = max(ans, best);
for(int i = L;i < min(start, L + 2 * bit);i++){
exclude(i);
}
}
}
}
long long findMaxAttraction(int N, int START, int DAYS, int ARR[]) {
n = N;
for(int i = 0;i < n;i++) arr[i+1] = ARR[i];
start = START + 1;
days = DAYS;
reset();
solve();
reverse(arr+1,arr+(n+1));
start = n - start + 1;
reset();
solve();
return ans;
}
