#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, start, d;
ll attraction[N], dp[N];
map<ll, int> cidx;
vector<ll> cval;
int walk(int l, int r) {
return r-l + min(start-l, r-start);
}
struct SegmentTree {
int n, l, r;
vector<ll> sum, cnt;
SegmentTree(int _n) : n(_n), l(0), r(-1) {
sum.assign(4*n, 0);
cnt.assign(4*n, 0);
}
void update(int idx, int l, int r, int x, ll val) {
if(r < x || x < l) return;
else if(l == r) {
sum[idx] += cval[l] * val;
cnt[idx] += val;
return;
}
int lc = idx<<1, rc = lc|1;
update(lc, l, (l+r)/2, x, val);
update(rc, (l+r)/2+1, r, x, val);
sum[idx] = sum[lc] + sum[rc];
cnt[idx] = cnt[lc] + cnt[rc];
}
ll queryKth(int idx, int l, int r, int k) {
if(k <= 0 || l > r) return 0;
if(cnt[idx] <= k) return sum[idx];
if(l == r) return k * cval[l];
int mid = (l+r)/2, lc = idx<<1, rc = lc|1;
if(k <= cnt[rc])
return queryKth(rc, mid+1, r, k);
else
return queryKth(rc, mid+1, r, cnt[rc]) + queryKth(lc, l, mid, k-cnt[rc]);
}
};
SegmentTree *st;
ll cost(int l, int r, int k) {
if(k <= 0) return 0;
while(st->r < r) st->update(1, 0, n-1, cidx[attraction[++st->r]], 1);
while(st->r > r) st->update(1, 0, n-1, cidx[attraction[st->r--]], -1);
while(st->l > l) st->update(1, 0, n-1, cidx[attraction[--st->l]], 1);
while(st->l < l) st->update(1, 0, n-1, cidx[attraction[st->l++]], -1);
return st->queryKth(1, 0, n-1, k);
}
void solve(int l, int r, int optL, int optR) {
if(l > r) return;
int mid = (l+r)>>1, best = -1;
ll& ret = dp[mid] = -1e15;
for(int i = optL; i <= optR; i++) {
ll cur = cost(mid, i, d - walk(mid, i));
if(ret < cur)
ret = cur, best = i;
}
solve(l, mid-1, optL, best);
solve(mid+1, r, best, optR);
}
ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
n = _n, start = _start, d = _d;
for(int i = 0; i < n; i++)
attraction[i] = _attraction[i];
for(int i = 0; i < n; i++)
cval.push_back(attraction[i]);
sort(cval.begin(), cval.end());
auto it = unique(cval.begin(), cval.end());
cval.erase(it, cval.end());
for(int i = 0; i < cval.size(); i++)
cidx[cval[i]] = i;
st = new SegmentTree(n);
solve(0, start, start, n-1);
ll ans = 0;
for(int i = 0; i <= start; i++)
ans = max(ans, dp[i]);
return ans;
}
