#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 = 50000;
int n;
int S;
int d;
vl w;
void reversedir(){
S = n-1-S;
reverse(all(w));
}
//////TOPK SECTION BEGINS
int k;
int topksize;
ll topksum;
int typ[mx]; //0--> unused, 1--> topk, 2--> couldtake
struct cmp1
{
bool operator()(const int& a, const int& b)
{
return w[a] > w[b];
}
};
struct cmp2
{
bool operator()(const int& a, const int& b)
{
return w[a] < w[b];
}
};
priority_queue<int, vector<int>, cmp1> topk; // top <= k
priority_queue<int, vector<int>, cmp2> couldtake; // not part of top k
void CLEAR(){
topksize = 0;
topksum = 0;
for(int i = 0; i < n; i++){
typ[i] = 0;
}
topk = priority_queue<int, vector<int>, cmp1>();
couldtake = priority_queue<int, vector<int>, cmp2>();
while(sz(topk)){
topk.pop();
}
while(sz(couldtake)){
couldtake.pop();
}
//Reset Everything
}
void REMOV(){ //removes irrelevant numbers from the top
while(sz(topk)){
if(typ[topk.top()] == 0){
topk.pop();
}
else break;
}
while(sz(couldtake)){
if(typ[couldtake.top()] == 0){
couldtake.pop();
}
else break;
}
}
void CHECK(){ //update couldtake, topk
REMOV();
while(sz(couldtake) && topksize < k){
REMOV();
int a = couldtake.top();
couldtake.pop();
assert(typ[a] == 2);
topk.push(a);
typ[a] = 1;
topksize++;
topksum+=w[a];
REMOV();
}
while(topksize == k && sz(couldtake)){
REMOV();
int a = couldtake.top();
int b = topk.top();
if(w[a] > w[b]){
couldtake.pop();
topk.pop();
typ[a] = 1;
typ[b] = 2;
topk.push(a);
couldtake.push(b);
topksum+=w[a];
topksum-=w[b];
}
else break;
}
REMOV();
}
void INSERT(int ind){
typ[ind] = 2;
couldtake.push(ind);
CHECK();
}
void ERASE(int ind){
assert(typ[ind] != 0);
if(typ[ind] == 1){
topksize--;
topksum-=w[ind];
}
typ[ind] = 0;
CHECK();
}
//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);
}
if(topksize == len){
ckmax(ans, topksum);
}
}
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
return 0;
}
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;
cout << lo << "\n";
for(int i = 0; i <= DIFF; i++){
ll ans1 = solvefixedlength(lo-i);
ll ans2 = solvefixedlength(lo+i);
if(i % 100 == 0) cout << i << " " << ans1 << " " << ans2 << "\n";
if(ans1 > ans){
cout << i << ans << "\n";
}
if(ans2 > ans){
cout << i << " " << ans << "\n";
}
ckmax(ans, ans1);
ckmax(ans, ans2);
}
//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();
}
