#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int pos[N], p[N], a[N], n, d;
struct Node {
ll sum; int cnt;
Node(ll sum = 0, int cnt = 0) :
sum(sum), cnt(cnt) {}
} t[N << 2];
Node merge(Node a, Node b) {
return Node(a.sum + b.sum, a.cnt + b.cnt);
}
void update(int node, int l, int r, int i, int x) {
if(l == r) {
if(x >= 0) t[node] = Node(x, 1);
else t[node] = Node(0, 0);
return;
} int m = l + r >> 1;
if(i <= m) update(node << 1, l, m, i, x);
else update(node << 1 | 1, m + 1, r, i, x);
t[node] = merge(t[node << 1], t[node << 1 | 1]);
}
ll query(int node, int k) {
if(t[node].cnt <= k) return t[node].sum;
if(t[node << 1].cnt >= k) return query(node << 1, k);
else return query(node << 1 | 1, k - t[node << 1].cnt) + t[node << 1].sum;
}
ll ans;
int start;
void recurr(int l, int r, int b, int e) {
if(l > r) return;
int m = l + r >> 1, opt;
ll mx = 0;
for(int i = l; i <= m; ++i)
update(1, 0, n - 1, pos[i], a[i]);
for(int i = e; i >= b; --i) {
update(1, 0, n - 1, pos[i], a[i]);
int k = d - (m - start) - (m - i);
if(k <= 0) break;
ll now = query(1, k);
if(now > mx) mx = now, opt = i;
}
if(mx > ans) ans = mx;
for(int i = e; i >= b; --i)
update(1, 0, n - 1, pos[i], -1);
recurr(m + 1, r, opt, e);
for(int i = l; i <= m; ++i)
update(1, 0, n - 1, pos[i], -1);
for(int i = e; i > opt; --i)
update(1, 0, n - 1, pos[i], a[i]);
recurr(l, m - 1, b, opt);
for(int i = e; i > opt; --i)
update(1, 0, n - 1, pos[i], -1);
}
void solve(int st) {
iota(p, p + n, 0);
sort(p, p + n, [](int i, int j) { return a[i] > a[j]; });
for(int i = 0; i < n; ++i) pos[p[i]] = i;
start = st;
recurr(st, min(n - 1, st + (d - 1) / 2), 0, st);
}
ll findMaxAttraction(int _n, int _start, int _d, int _a[]) {
n = _n, d = _d;
copy(_a, _a + n, a);
solve(_start);
reverse(a, a + n);
solve(n - _start - 1);
return ans;
}
