#include "holiday.h"
#include <stdio.h>
#define N 100000
#define A 100000000
#define LG 30 /* LG = ceil(log2(A)) */
#define N_ (N * (LG + 1))
int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int ll[1 + N_], rr[1 + N_], kk[1 + N_], _; long long xx[1 + N_];
int update(int t, int l, int r, int i, int x) {
int t_ = _++;
kk[t_] = kk[t] + 1, xx[t_] = xx[t] + x;
if (r - l > 1) {
int m = (l + r) / 2;
if (i < m)
ll[t_] = update(ll[t], l, m, i, x), rr[t_] = rr[t];
else
ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i, x);
}
return t_;
}
long long query(int t, int k) {
int l, r, m;
long long sum;
l = 0, r = A + 1, sum = 0;
while (r - l > 1) {
m = (l + r) / 2;
if (k < kk[ll[t]])
r = m, t = ll[t];
else
l = m, k -= kk[ll[t]], sum += xx[ll[t]], t = rr[t];
}
sum += (long long) min(kk[t], k) * (A - l);
return sum;
}
int tt[N];
void solve_(long long *dp, int l, int r, int il, int ir, int c) {
int m, i, im;
long long d_;
if (l == r)
return;
m = (l + r) / 2;
im = -1, d_ = -1;
for (i = il; i < ir; i++) {
long long d = m - i * c < 0 ? -1 : query(tt[i], m - i * c);
if (d_ < d)
d_ = d, im = i;
}
dp[m] = d_;
solve_(dp, l, m, il, ir, c), solve_(dp, m + 1, r, il, ir, c);
}
void solve(int *aa, long long *dp1, long long *dp2, int n) {
int i, t;
_ = 1;
for (i = 0, t = 0; i < n; i++)
tt[i] = t = update(t, 0, A + 1, A - aa[i], aa[i]);
solve_(dp1, 0, n * 2, 0, n, 1);
solve_(dp2, 0, n * 3, 0, n, 2);
}
long long findMaxAttraction(int n, int s, int d_, int aa[]) {
static int aa_[N];
static long long dp1[N * 2], dp2[N * 3], dq1[N * 2], dq2[N * 3];
int i, d;
long long ans;
for (i = s; i >= 0; i--)
aa_[s - i] = aa[i];
solve(aa_, dp1, dp2, s + 1);
for (i = s + 1; i < n; i++)
aa_[i - s - 1] = aa[i];
solve(aa_, dq1, dq2, n - 1 - s);
for (d = d_; d >= 0; d--)
dq1[d] = d == 0 ? 0 : dq1[d - 1], dq2[d] = d < 2 ? 0 : dq2[d - 2];
ans = 0;
for (d = 0; d <= d_; d++)
ans = max(ans, max(dq2[d] + dp1[d_ - d], dp2[d] + dq1[d_ - d]));
return ans;
}
