#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int start, L=0, R=-1, n;
vector<pii> vect;
vector<vector<int> > ll, rr;
struct node{
int s, e, m, val, c;
node *l, *r;
node(int S, int E){
s=S, e=E, m=(s+e)/2, val=0, c=0;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void up(int i, int v){
if (s==e)val+=v, c=!c;
else{
if (i<=m)l->up(i, v);
else r->up(i, v);
val=l->val+r->val;
c=l->c+r->c;
}
}
int bsta(int k){
if (s==e)return s;
if (r->c>=k)return r->bsta(k);
return l->bsta(k-r->c);
}
int query(int left, int right){
if (s==left && e==right)return val;
if (right<=m)return l->query(left, right);
else if (left>m)return r->query(left, right);
else return l->query(left, m)+r->query(m+1, right);
}
}*st;
int cost(int l, int r, int d){
if (d<0)return LLONG_MIN/2;
if (!d)return 0;
while(R<r)++R, st->up(vect[R].se, vect[R].fi);
while(l<L)--L, st->up(vect[L].se, vect[L].fi);
while(r<R)st->up(vect[R].se, -vect[R].fi), --R;
while (L<l)st->up(vect[L].se, -vect[L].fi), ++L;
return st->query(st->bsta(d), n-1);
}
void dncl(int l, int r, int optl, int optr, bool t){
if (l>r)return;
int mid=(l+r)/2, best=LLONG_MIN/2, opt;
for (int i=optr; i>=optl; --i){
int res=cost(i, start-1, mid-(start-i)*(1+t));
if (res>best)best=res, opt=i;
}
ll[mid][t]=best;
dncl(l, mid-1, opt, optr, t);
dncl(mid+1, r, optl, opt, t);
}
void dncr(int l, int r, int optl, int optr, bool t){
if (l>r)return;
int mid=(l+r)/2, best=LLONG_MIN/2, opt;
for (int i=optl; i<=optr; ++i){
int res=cost(start+1, i, mid-(i-start)*(1+t));
if (res>best)best=res, opt=i;
}
rr[mid][t]=best;
dncr(l, mid-1, optl, opt, t);
dncr(mid+1, r, opt, optr, t);
}
int findMaxAttraction(signed N, signed Start, signed d, signed attraction[]){
n=N;
start=Start;
vect.resize(n);
ll.resize(d+1, vector<int>(2, 0));
rr.resize(d+1, vector<int>(2, 0));
st = new node(0, n-1);
vector<pii> temp(n);
for (int i=0; i<n; ++i)temp[i]=mp(attraction[i], i);
sort(temp.begin(), temp.end());
for (int i=0; i<n; ++i)vect[temp[i].se]=mp(temp[i].fi, i);
if (start)dncl(1, d, 0, start-1, 0);
if (start)dncl(1, d, 0, start-1, 1);
if (start!=n-1)dncr(1, d, start+1, n-1, 0);
if (start!=n-1)dncr(1, d, start+1, n-1, 1);
int ans=0;
for (int i=0; i<=d; ++i){
ans=max({ans, ll[i][0]+rr[d-i][1], ll[i][1]+rr[d-i][0]});
if (i!=d)ans=max({ans, ll[i][0]+rr[d-i-1][1]+vect[start].fi, ll[i][1]+rr[d-i-1][0]+vect[start].fi});
}
return ans;
}
