#include"holiday.h"
#include <map>
#include <vector>
#include <algorithm>
#define LL long long
#define MAXN 100005
using namespace std;
LL ans;
int A[MAXN], D, S, N;
map <int,int> Lookup;
vector <int> Sweep;
int Val[MAXN];
class DS {
LL ST[MAXN * 4][2];
void pushup(int cur) {
ST[cur][0] = ST[2*cur][0] + ST[2*cur+1][0];
ST[cur][1] = ST[2*cur][1] + ST[2*cur+1][1];
}
public:
void nuke(int l=0, int r=N-1, int cur=1) {
ST[cur][0] = ST[cur][1] = 0;
if (l != r) {
int mid = (l + r) >> 1;
nuke(l, mid, 2*cur);
nuke(mid+1, r, 2*cur+1);
}
}
void upd(bool b, int ind, int l, int r, int cur) {
if (ind < l || ind > r) {return;}
if (l == r) {
ST[cur][1] += b ? 1 : -1;
ST[cur][0] = Val[l] * ST[cur][1];
} else {
int mid = (l + r) >> 1;
upd(b, ind, l, mid, 2*cur);
upd(b, ind, mid+1, r, 2*cur+1);
pushup(cur);
}
}
LL kth(int k, int l, int r, int cur) {
if (l == r) {
return(((LL) Val[l])*(min((LL) k, ST[cur][1])));
} else {
int mid = (l + r) >> 1;
if (ST[2*cur+1][1] <= k) { //early exit?
return(ST[2*cur+1][0] +
kth(k - ST[2*cur+1][1], l, mid, 2*cur));
} else {
return(kth(k, mid+1, r, 2*cur+1));
}
}
}
void add(int v) {
upd(1, Lookup[v], 0, N-1, 1);
}
void del(int v) {
upd(0, Lookup[v], 0, N-1, 1);
}
LL ask(int x) {
if (x < 0) {return(-1LL<<60);}
return(kth(x, 0, N-1, 1));
}
} KQ;
void Compress() {
for (int i=0; i<N; i++) {
Sweep.push_back(A[i]);
}
sort(Sweep.begin(), Sweep.end());
int pt = 0;
for (int i=0; i<N; i++) {
if (Sweep[i] == 0 || Sweep[i] != Sweep[i-1]) {
Val[pt] = Sweep[i];
Lookup[Sweep[i]] = pt;
pt++;
}
}
}
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];}
Compress();
slvL();
for (int i=0; i<=n/2; i++) {
swap(A[i], A[n-1-i]);
}
S = N - 1 - S;
slvL();
return(ans);
}
