#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.ST << ", " << p.ND << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
template<class T> int size(T && a) { return (int) a.size(); }
using LL = long long;
using PII = pair<int, int>;
#include"holiday.h"
struct SegTree {
using T = pair<LL, int>;
vector<T> tree;
int sz = 1;
T f(T a, T b) {
T ret = {0, 0};
if(a.ND != 0) {
ret.ST += a.ST;
ret.ND += a.ND;
}
if(b.ND != 0) {
ret.ST += b.ST;
ret.ND += b.ND;
}
return ret;
}
SegTree(vector<int> a) {
int n = size(a);
while(sz < n) sz *= 2;
tree.resize(sz * 2);
REP(i, n) tree[i + sz].ST = a[i];
}
void update(int v, int q) {
tree[v += sz].ND = q;
while(v /= 2)
tree[v] = f(tree[v * 2], tree[v * 2 + 1]);
}
LL query(int k) {
int v = 1;
LL ret = 0;
while(v < sz) {
if(k < tree[v * 2].ND) v *= 2;
else {
k -= tree[v * 2].ND;
if(tree[v * 2].ND)
ret += tree[v * 2].ST;
v = v * 2 + 1;
}
}
return ret;
}
};
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
auto get_on_right = [&](int cost) {
vector<int> a(n), per(n);
REP(i, n) {
a[i] = attraction[i];
per[i] = i;
}
debug(a);
sort(per.begin(), per.end(), [&](int i, int j) {
return a[i] > a[j];
});
sort(a.rbegin(), a.rend());
vector<int> ord(n);
REP(i, n) ord[per[i]] = i;
SegTree tree(a);
vector<LL> ret(d + 1);
auto solve = [&](auto self, int d_l, int d_r, int opt_l, int opt_r) {
if(opt_l > opt_r) return;
if(d_l > d_r) {
FOR(i, opt_l, opt_r)
tree.update(ord[i], true);
return;
}
int cur_d = (d_l + d_r) / 2;
pair<LL, int> best = {0, opt_l};
FOR(i, opt_l, opt_r) {
tree.update(ord[i], true);
LL x = tree.query(cur_d - cost * (i - start));
best = max(best, {x, i});
}
FOR(i, opt_l, opt_r)
tree.update(ord[i], false);
int opt = best.ND;
ret[cur_d] = best.ST;
self(self, d_l, cur_d - 1, opt_l, opt);
tree.update(ord[opt], false);
self(self, cur_d + 1, d_r, opt, opt_r);
};
solve(solve, 0, d, start + cost - 1, n - 1);
FOR(i, start, n - 1)
tree.update(ord[i], false);
return ret;
};
auto rev = [&]() {
reverse(attraction, attraction + n);
start = n - 1 - start;
};
auto left_then_right = [&]() {
auto A = get_on_right(1);
rev();
auto B = get_on_right(2);
FOR(i, 0, d)
debug(i, A[i], B[i]);
LL ret = 0;
FOR(i, 0, d)
ret = max(ret, A[i] + B[d - i]);
return ret;
};
return max(left_then_right(), left_then_right());
}
