#include "holiday.h"
#include <bits/stdc++.h>
// mrrrrow meeeow :3
// go play vivid/stasis! it's free on steam
#define f first
#define s second
using namespace std;
const int N = 1 << 17;
pair<int, long long> st[N * 2];
int to_sorted[100000];
pair<int, int> sorted[100000];
long long resl[250001], resll[250001];
long long resr[250001], resrl[250001];
long long get(int x) {
long long res = 0;
for (int i = 1; x > 0 && i < N;) {
if (st[i*2+1].f > x) {
i = i*2+1;
} else {
i = i*2;
x -= st[i+1].f;
res += st[i+1].s;
if (st[i].f <= x) {
res += st[i].s;
break;
}
}
}
return res;
}
int off = 0;
void activate(int i) {
i = N + to_sorted[off + i];
st[i] = {1, sorted[i - N].f};
for (i /= 2; i > 0; i /= 2) st[i] = {st[i*2].f + st[i*2+1].f, st[i*2].s + st[i*2+1].s};
}
void deactivate(int i) {
i = N + to_sorted[off + i];
st[i] = {0, 0};
for (i /= 2; i > 0; i /= 2) st[i] = {st[i*2].f + st[i*2+1].f, st[i*2].s + st[i*2+1].s};
}
long long recurse(int dl, int dr, int rl, int rr, long long res[], int mul=1) {
int d = (dl + dr) / 2;
int r = rl - 1;
long long m = get(d - r*mul);
for (int i = rl; i <= rr; i++) {
activate(i);
long long nm = get(d - i*mul);
if (nm > m) r = i, m = nm;
}
res[d] = m;
for (int i = r; i <= rr; i++) deactivate(i);
if (d + 1 <= dr) recurse(d + 1, dr, r, rr, res, mul);
for (int i = rl; i < r; i++) deactivate(i);
if (dl <= d - 1) res[d] = max(res[d], recurse(dl, d - 1, rl, r, res, mul));
return res[d];
}
long long findMaxAttraction(int n, int s, int d, int attraction[]) {
reverse(attraction, attraction + s);
for (int i = 0; i < n; i++) sorted[i] = {attraction[i], i};
sort(sorted, sorted + n);
for (int i = 0; i < n; i++) to_sorted[sorted[i].s] = i;
recurse(0, d-1, 0, s - 1, resl+1);
for (int i = 1; i < 2*N; i++) st[i] = {0, 0};
recurse(0, d-1, 0, s - 1, resll+1, 2);
for (int i = 1; i < 2*N; i++) st[i] = {0, 0}; off = s;
recurse(0, d, 0, n - s - 1, resr);
for (int i = 1; i < 2*N; i++) st[i] = {0, 0};
recurse(0, d, 0, n - s - 1, resrl, 2);
long long res = 0;
for (int i = 0; i <= d; i++) res = max(res, max(resl[i] + resrl[d - i], resll[i] + resr[d - i]));
return res;
}
