#include "holiday.h"
#include <algorithm>
#include <iostream>
#include <utility>
// meow mrrow nya nya :3c
// play vivid/stasis. free on steam
using namespace std;
const int N = 1 << 17;
pair<long long, int> sg1[N * 2];
pair<int, int> so1[N];
int rs1[N];
int fs[N * 3];
long long fsv[N * 3];
pair<long long, int> sg2[N * 2];
pair<int, int> so2[N];
int rs2[N];
int gs[N * 3];
long long gsv[N * 3];
void set_ac1(int i, bool v) {
i += N;
sg1[i].second = v;
i /= 2;
sg1[i].first = sg1[i * 2].first * sg1[i * 2].second + sg1[i * 2 + 1].first * sg1[i * 2 + 1].second;
sg1[i].second = sg1[i * 2].second + sg1[i * 2 + 1].second;
for (i /= 2; i > 0; i /= 2)
sg1[i].first = sg1[i * 2].first + sg1[i * 2 + 1].first, sg1[i].second = sg1[i * 2].second + sg1[i * 2 + 1].second;
}
void set_ac2(int i, bool v) {
i += N;
sg2[i].second = v;
i /= 2;
sg2[i].first = sg2[i * 2].first * sg2[i * 2].second + sg2[i * 2 + 1].first * sg2[i * 2 + 1].second;
sg2[i].second = sg2[i * 2].second + sg2[i * 2 + 1].second;
for (i /= 2; i > 0; i /= 2)
sg2[i].first = sg2[i * 2].first + sg2[i * 2 + 1].first, sg2[i].second = sg2[i * 2].second + sg2[i * 2 + 1].second;
}
pair<long long, int> lx1(int x, int i = 1) {
if (sg1[i].second <= x) {
if (i >= N) return {sg1[i].first * sg1[i].second, sg1[i].second};
return sg1[i];
}
pair<long long, int> l = lx1(x, i * 2);
if (l.second < x) {
pair<long long, int> r = lx1(x - l.second, i * 2 + 1);
l.first += r.first, l.second += r.second;
}
return l;
}
pair<long long, int> lx2(int x, int i = 1) {
if (sg2[i].second <= x) {
if (i >= N) return {sg2[i].first * sg2[i].second, sg2[i].second};
return sg2[i];
}
pair<long long, int> l = lx2(x, i * 2);
if (l.second < x) {
pair<long long, int> r = lx2(x - l.second, i * 2 + 1);
l.first += r.first, l.second += r.second;
}
return l;
}
int f(int d, int l, int r) {
int mi = 0;
long long m = 0;
for (int i = l; i < r && d - i > 0; i++) {
set_ac1(rs1[i], true);
long long c = lx1(d - i).first;
if (c > m) m = c, mi = i;
}
fs[d] = mi;
fsv[d] = m;
return mi;
}
int g(int d, int l, int r) {
int mi = 0;
long long m = 0;
for (int i = l; i < r && d - i > 0; i++) {
set_ac2(rs2[i], true);
long long c = lx2(d - i).first;
if (c > m) m = c, mi = i;
}
gs[d] = mi;
gsv[d] = m;
return mi;
}
void recf(int ml, int mr, int l, int r) {
int mm = (ml + mr) / 2;
f(mm, l, r);
if (ml == mr) return;
for (int i = l; i < r; i++) set_ac1(i, false);
if (mm - 1 >= ml) recf(ml, mm - 1, l, fs[mm] + 1);
for (int i = 0; i <= fs[mm]; i++) set_ac1(i, true);
if (mm + 1 <= mr) recf(mm + 1, mr, fs[mm], r);
}
void recg(int ml, int mr, int l, int r) {
int mm = (ml + mr) / 2;
g(mm, l, r);
if (ml == mr) return;
for (int i = l; i < r; i++) set_ac2(i, false);
if (mm - 1 >= ml) recg(ml, mm - 1, l, gs[mm] + 1);
for (int i = 0; i <= gs[mm]; i++) set_ac2(i, true);
if (mm + 1 <= mr) recg(mm + 1, mr, gs[mm], r);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
int n1 = n - start;
int n2 = start;
for (int i = 0; i < n1; i++) so1[i].first = attraction[n2 + i], so1[i].second = i;
sort(so1, so1 + n1, [](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });
for (int i = 0; i < n1; i++) sg1[N + i].first = so1[i].first, rs1[so1[i].second] = i;
for (int i = 0; i < n2; i++) so2[n2 - i - 1].first = attraction[i], so2[i].second = i;
sort(so2, so2 + n2, [](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });
for (int i = 0; i < n2; i++) sg2[N + i].first = so2[i].first, rs2[so2[i].second] = i;
recf(1, d, 0, n1);
recg(1, d, 0, n2);
long long res = gsv[d - 1];
for (int d0 = 0; d0 <= d; d0++) {
int g0 = d - d0 - fs[d0] - 1;
long long nres = fsv[d0] + (g0 > 0 ? gsv[g0] : 0);
if (nres > res) res = nres;
}
return res;
}
