#include"holiday.h"
#include<bits/stdc++.h>
#define fi first
#define sc second
using namespace std;
const int maxn = 2e5 + 10;
long long f[2 * maxn], g[2 * maxn];
int a[maxn], b[maxn], tmp[maxn], R;
typedef pair<long long, int> LI;
struct IT {
int cnt[4 * maxn];
long long sum[4 * maxn];
void update(int r, int lo, int hi, int u, int val) {
if (lo == hi) {
cnt[r] += val;
sum[r] += tmp[lo] * val;
return;
}
int mid = (lo + hi)/2;
if (u <= mid)
update(r * 2, lo, mid, u, val);
else
update(r * 2 + 1, mid + 1, hi, u, val);
sum[r] = sum[r * 2] + sum[r * 2 + 1];
cnt[r] = cnt[r * 2] + cnt[r * 2 + 1];
}
long long get(int r, int lo, int hi, int S) {
if (lo == hi)
return tmp[lo] * min(S, cnt[r]);
int mid = (lo + hi)/2;
if (cnt[r * 2 + 1] <= S)
return sum[r * 2 + 1] + get(r * 2, lo, mid, S - cnt[r * 2 + 1]);
return get(r * 2 + 1, mid + 1, hi, S);
}
} tree;
int last = 0;
void shift(int a[], int to) {
while (last < to) {
tree.update(1, 1, R, a[++last], 1);
}
while (last > to) {
tree.update(1, 1, R, a[last--], -1);
}
}
void compute(long long f[], int a[], int l, int r, int optL, int optR, bool turn_back) {
if (l > r || optL > optR)
return;
int m = (l + r)/2;
LI best = LI(0, -2e9);
for (int i = optL; i <= min(m, optR); ++i) {
if ((i - 1) + (i - 1) * turn_back > m)
break;
shift(a, i);
best = max(best, LI(tree.get(1, 1, R, m - (i - 1) - (i - 1) * turn_back), -i));
}
f[m] = best.fi;
int opt = -best.sc;
compute(f, a, l, m - 1, optL, opt, turn_back);
compute(f, a, m + 1, r, opt, optR, turn_back);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
++start;
for (int i = 1; i <= n; ++i) {
tmp[i] = attraction[i - 1];
}
sort(tmp + 1, tmp + n + 1);
R = unique(tmp + 1, tmp + n + 1) - tmp - 1;
for (int i = 1; i <= n; ++i)
attraction[i - 1] = lower_bound(tmp + 1, tmp + R + 1, attraction[i - 1]) - tmp;
for (int i = 1; i <= start; ++i)
a[i] = attraction[i - 1];
reverse(a + 1, a + start + 1);
for (int i = start + 1; i <= n; ++i)
b[i - start] = attraction[i - 1];
compute(f, a, 1, d, 1, start, 1);
shift(a, 0);
compute(g, b, 1, d, 1, n - start, 0);
long long ans = 0;
for (int i = 0; i <= d; ++i)
ans = max(ans, f[i] + g[d - i - 1]);
shift(b, 0);
compute(f, a, 1, d, 1, start, 0);
shift(a, 0);
compute(g, b, 1, d, 1, n - start, 1);
for (int i = 0; i <= d; ++i)
ans = max(ans, g[i] + f[d - i - 2]);
return ans;
}
