#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long ll;
int n, start, d, a[100005], b[100005], rev[100005];
vector<int> disc, vec[100005];
ll ans;
int cnt(vector<pair<int, ll> > val, int l, int r) {
return upper_bound(val.begin(), val.end(), mp(r, (ll)1e16)) - lower_bound(val.begin(), val.end(), mp(l, 0ll));
}
ll sum(vector<pair<int, ll> > val, int l, int r) {
int p2 = upper_bound(val.begin(), val.end(), mp(r, (ll)1e16)) - val.begin();
if (p2 == 0) return 0;
p2--;
int p1 = lower_bound(val.begin(), val.end(), mp(l, 0ll)) - val.begin();
return val[p2].second - (p1 ? val[p1 - 1].second : 0ll);
}
struct node {
node *left, *right;
int S, E;
vector<pair<int, ll> > val;
node(int _s, int _e) : S(_s), E(_e) {
if (S == E) {
sort(vec[S].begin(), vec[S].end());
val.resize(vec[S].size());
ll prf = 0;
for (int j = 0; j < vec[S].size(); j++) {
prf += a[vec[S][j]];
val[j] = mp(vec[S][j], prf);
}
return;
}
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
merge(left->val.begin(), left->val.end(), right->val.begin(), right->val.end(), back_inserter(val));
ll prf = 0;
for (int j = 0; j < val.size(); j++) {
prf += a[val[j].first];
val[j].second = prf;
}
}
ll qry(int l, int r, int k) { // sum of k largest elements in [l, r]
if (S == E) return (ll)min(cnt(val, l, r), k) * (ll)rev[S];
if (cnt(right->val, l, r) >= k) return right->qry(l, r, k);
else {
ll ans = left->qry(l, r, k - cnt(right->val, l, r));
assert(ans >= 0);
return ans + sum(right->val, l, r);
}
}
} *root;
void dnc(int l, int r, int x, int y) {
if (l > r || x > y) return;
int m = (l + r) >> 1, opt = -1;
ll cur = -1;
for (int i = x; i <= y; i++) {
if (d - 2 * (start - m) - (i - start) < 0) break;
ll tmp = root->qry(m, i, d - 2 * (start - m) - (i - start));
assert(tmp >= 0);
if (tmp > cur) {
cur = tmp;
opt = i;
}
}
ans = max(ans, cur);
assert(opt != -1);
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.pb(a[i]);
}
sort(disc.begin(), disc.end());
disc.erase(unique(disc.begin(), disc.end()), disc.end());
for (int i = 0; i < n; i++) {
b[i] = lower_bound(disc.begin(), disc.end(), a[i]) - disc.begin() + 1;
vec[b[i]].pb(i);
rev[b[i]] = a[i];
}
root = new node(1, disc.size());
dnc(0, start, start + 1, n - 1);
reverse(a, a + n);
start = n - start - 1;
for (int i = 1; i <= disc.size(); i++) vec[i].clear();
for (int i = 0; i < n; i++) {
b[i] = lower_bound(disc.begin(), disc.end(), a[i]) - disc.begin() + 1;
vec[b[i]].pb(i);
rev[b[i]] = a[i];
}
root = new node(1, disc.size());
dnc(0, start, start + 1, n - 1);
return ans;
}
