#include "holiday.h"
#include <bits/stdc++.h>
#define upmax(a,b) (a)=max((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
const int MAXN = 100055;
struct NOD {
NOD *l, *r;
ll sum;
int cnt;
NOD();
} *nil, *pst[MAXN];
NOD :: NOD() {
l = r = nil;
sum = cnt = 0;
}
int A[MAXN], AO[MAXN], ARO[MAXN];
ll Ans;
int N, X, L;
void makeTree(NOD *bf, NOD *nw, int s, int e, int x, int r) {
nw -> cnt = bf -> cnt + 1;
nw -> sum = bf -> sum + r;
if(s == e) return;
int m = (s+e) >> 1;
if(x <= m) {
nw -> r = bf -> r;
nw -> l = new NOD();
makeTree(bf -> l, nw -> l, s, m, x, r);
} else {
nw -> l = bf -> l;
nw -> r = new NOD();
makeTree(bf -> r, nw -> r, m+1, e, x, r);
}
}
ll get(NOD *bf, NOD *nw, int x) {
if(!x) return 0;
if(nw->cnt - bf->cnt == x) return nw->sum - bf->sum;
int lc = nw->l->cnt - bf->l->cnt;
if(x <= lc) return get(bf->l, nw->l, x);
return (nw->l->sum - bf->l->sum) + get(bf->r, nw->r, x-lc);
}
ll get(int s, int e, int x) {
return get(pst[s-1], pst[e], x);
}
void f(int s, int e, int p, int q) {
if(s > e || p > q) return;
int m = (s+e) >> 1;
ll hc = -INFLL; int hi = -1;
for(int x = p, xe = min({N, (L+X+m)/2, q}); x <= xe; x++) {
ll t = get(m, x, min(x-m+1, L-(x+x-m-X)));
if(t <= hc) continue;
hc = t;
hi = x;
}
upmax(Ans, hc);
f(s, m-1, p, hi);
f(m+1, e, hi, q);
}
ll getAns() {
nil = new NOD();
nil->l = nil->r = nil;
nil->sum = nil->cnt = 0;
iota(AO, AO+N+1, 0);
sort(AO+1, AO+N+1, [&](int a, int b) {
return A[a] > A[b];
});
for(int i = 1; i <= N; i++) ARO[AO[i]] = i;
pst[0] = nil;
for(int i = 1; i <= N; i++) {
pst[i] = new NOD();
makeTree(pst[i-1], pst[i], 1, N, ARO[i], A[i]);
}
f(max(1, X-L), X, X, N);
X = N+1-X;
reverse(A+1, A+N+1);
iota(AO, AO+N+1, 0);
sort(AO+1, AO+N+1, [&](int a, int b) {
return A[a] > A[b];
});
for(int i = 1; i <= N; i++) ARO[AO[i]] = i;
for(int i = 1; i <= N; i++) {
pst[i] = new NOD();
makeTree(pst[i-1], pst[i], 1, N, ARO[i], A[i]);
}
f(max(1, X-L), X, X, N);
return Ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
::N = n;
::X = start + 1;
::L = d;
for(int i = 0; i < n; i++)
::A[i+1] = attraction[i];
return getAns();
}
