#include "holiday.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int n, d;
int start;
int st, en;
long long ans;
int s[N], id[N];
pair<int, long long> seg[N * 2];
pair<int, long long> merge(pair<int, long long> x, pair<int, long long> y) {
return make_pair(x.first + y.first, x.second + y.second);
}
void upd(int nd, int l, int r, int p, int v) {
if (l == r) {
seg[nd].first += v;
seg[nd].second += v * s[l];
return;
}
int mid = (l + r) / 2;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p, v);
} else {
upd(rs, mid + 1, r, p, v);
}
seg[nd] = merge(seg[nd + 1], seg[rs]);
}
long long dive(int nd, int l, int r, int k) {
if (l == r) {
return seg[nd].second;
}
int mid = (l + r) / 2;
int rs = nd + ((mid - l + 1) << 1);
if (seg[rs].first >= k) {
return dive(rs, mid + 1, r, k);
}
return dive(nd + 1, l, mid, k - seg[rs].first) + seg[rs].second;
}
void edit(int l, int r) {
while (st > l) upd(0, 0, n - 1, id[--st], 1);
while (en < r) upd(0, 0, n - 1, id[++en], 1);
while (st < l) upd(0, 0, n - 1, id[st++], -1);
while (en > r) upd(0, 0, n - 1, id[en--], -1);
}
void solve(int l, int r, int optl, int optr) {
if (l > r || optl > start) return;
int mid = (l + r) / 2;
if (mid > start) {
return solve(l, mid - 1, optl, optr);
}
pair<long long, int> opt;
for (int i = max(optl, mid); i <= optr; ++i) {
edit(mid, i);
if (i >= start) {
int rem = 0;
rem = max(rem, d - ((start - mid) * 2 + i - start));
rem = max(rem, d - ((i - start) * 2 + start - mid));
opt = max(opt, make_pair(dive(0, 0, n - 1, rem), i));
}
}
ans = max(ans, opt.first);
//cout << "mid, opt: " << mid << ' ' << opt.first << ' ' << opt.second << '\n';
solve(l, mid - 1, optl, opt.second);
solve(mid + 1, r, opt.second, optr);
}
long long int findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
n = n_; d = d_;
start = start_;
for (int i = 0; i < n; ++i) {
s[i] = attraction[i];
}
sort(s, s + n);
for (int i = 0; i < n; ++i) {
id[i] = lower_bound(s, s + n, attraction[i]) - s;
}
st = 1, en = 0;
solve(0, n - 1, 0, n - 1);
return ans;
}
