#include"holiday.h"
#include <map>
#define LL long long
#define MAXN 100005
using namespace std;
class DS {
map <int,int> M;
public:
void nuke() {M.clear();}
void add(int v) {
M[v]++;
}
void del(int v) {
M[v]--;
}
LL ask(int num) {
if (M.empty()) {return(0);}
if (num < 0) {return(-1LL<<60);}
LL res = 0;
auto pt = --M.end();
while (num) {
if ((*pt).second > num) {
res += ((LL) num) * ((LL) (*pt).first);
num = 0;
} else {
res += ((LL) (*pt).second) * ((LL) (*pt).first);
num -= (*pt).second;
}
if (pt == M.begin()) {break;}
else {--pt;}
}
return(res);
}
} KQ;
LL ans;
int A[MAXN], D, S, N;
void slv(int l, int r, int lo, int hi, int pl, int pr) {
//printf("%d %d %d %d\n",l,r,lo,hi);
if (l > r) {return;}
int p = (l + r) >> 1;
int pL = pl, pR = pr;
while (pl > hi+1) {
KQ.add(A[pl-1]);
pl--;
}
while (pr < p) {
KQ.add(A[pr+1]);
pr++;
}
while (pl <hi+1) {
KQ.del(A[pl]);
pl++;
}
while (pr > p) {
KQ.del(A[pr]);
pr--;
}
LL opt=-1, optval=-1LL<<60;
for (int i=hi; i>=lo; i--) {
KQ.add(A[i]);
LL res = KQ.ask(D-S + 2*i - p);
if (res >= optval) {
opt = i;
optval = res;
ans = max(ans, res);
}
}
slv(l, p-1, lo, opt, lo, p);
slv(p+1,r, opt, hi, lo, p);
//reset pos
while (lo < pL) {
KQ.del(A[lo]);
lo++;
}
while (lo > pL) {
KQ.add(A[lo-1]);
lo--;
}
while (p < pR) {
KQ.add(A[p+1]);
p++;
}
while (p > pR) {
KQ.del(A[p]);
p--;
}
}
void slvL() {
for (int i=S; i>=0; i--) { //one direction
KQ.add(A[i]);
ans = max(ans, KQ.ask(D-S+i));
}
slv(S+1, N-1, 0, S-1, 0, S);
KQ.nuke();
}
LL findMaxAttraction(int n, int s, int d, int a[]) { //len, start, days, val
N = n, S = s, D = d;
for (int i=0; i<n; i++) {A[i] = a[i];}
slvL();
for (int i=0; i<=n/2; i++) {
swap(A[i], A[n-1-i]);
}
S = N - 1 - S;
/*for (int i=0; i<N; i++) {
printf("%d ",A[i]);
}
printf("\n%d\n",S);
printf(" Flip\n"); */
slvL();
return(ans);
}
