#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int L, R, n, start, d, a[100005], rev[100005], disc[100005];
ll ans;
pair<ll, int> ft[100005];
vector<int> disc_v;
inline int ls(int x) { return x & -x; }
void add(int x) {
for (int y = disc[x]; y <= disc_v.size(); y += ls(y))
ft[y].first += a[x], ft[y].second++;
}
void del(int x) {
for (int y = disc[x]; y <= disc_v.size(); y += ls(y))
ft[y].first -= a[x], ft[y].second--;
}
pair<ll, int> qry(int x) {
pair<ll, int> ret = make_pair(0ll, 0);
for (; x; x -= ls(x))
ret.first += ft[x].first, ret.second += ft[x].second;
return ret;
}
ll cost(int k) { // sum of largest k things inside container
if (k <= 0) return 0;
if (k >= qry(disc_v.size()).second) return qry(disc_v.size()).first;
int curr = 0, rs = 0;
for (int i = 17; i >= 0; i--)
if (curr + (1 << i) <= disc_v.size() && ft[curr + (1 << i)].second + rs < k) {
rs += ft[curr + (1 << i)].second;
curr += (1 << i);
}
return qry(curr).first + (ll)(k - rs) * rev[curr + 1];
}
void shift(int l, int r) {
while (l < L) add(--L);
while (r > R) add(++R);
while (l > L) del(L++);
while (r < R) del(R--);
}
void dnc(int l, int r, int x, int y) {
if (l > r) return;
int m = (l + r) >> 1, opt = -1;
ll curr = -1, tmp;
for (int i = y; i >= x; i--) {
shift(i, m);
tmp = cost(d - 2 * (m - start) - (start - i));
if (tmp > curr) {
curr = tmp;
opt = i;
}
}
assert(opt != -1);
ans = max(ans, curr);
dnc(l, m - 1, x, opt);
dnc(m + 1, r, opt, y);
}
ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
n = _n;
start = _start;
d = _d;
for (int i = 0; i < n; i++) {
a[i] = _attraction[i];
disc_v.push_back(a[i]);
}
sort(disc_v.begin(), disc_v.end());
disc_v.erase(unique(disc_v.begin(), disc_v.end()), disc_v.end());
for (int i = 0; i < n; i++) {
disc[i] = disc_v.size() - (lower_bound(disc_v.begin(), disc_v.end(), a[i]) - disc_v.begin() + 1) + 1;
rev[disc[i]] = a[i];
}
L = R = start;
add(start);
for (int i = start; i < n; i++) {
shift(start, i);
ans = max(ans, cost(d - (i - start)));
}
for (int i = start - 1; i >= 0; i--) {
shift(i, start);
ans = max(ans, cost(d - (start - i)));
}
dnc(start, n - 1, 0, start);
_start = _n - _start - 1;
reverse(_attraction, _attraction + _n);
memset(a, 0, sizeof a);
memset(rev, 0, sizeof rev);
memset(disc, 0, sizeof disc);
for (int i = 1; i <= n; i++) ft[i] = make_pair(0ll, 0);
disc_v.clear();
n = _n;
start = _start;
d = _d;
for (int i = 0; i < n; i++) {
a[i] = _attraction[i];
disc_v.push_back(a[i]);
}
sort(disc_v.begin(), disc_v.end());
disc_v.erase(unique(disc_v.begin(), disc_v.end()), disc_v.end());
for (int i = 0; i < n; i++) {
disc[i] = disc_v.size() - (lower_bound(disc_v.begin(), disc_v.end(), a[i]) - disc_v.begin() + 1) + 1;
rev[disc[i]] = a[i];
}
L = R = start;
add(start);
dnc(start, n - 1, 0, start);
return ans;
}
