#include"holiday.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 100010;
int a[MAXN];
int solve1(int n, int st, int d) {
int sum = 0;
priority_queue<int, vector<int>, greater<int>> pq;
int res = 0;
For(i, st, min(st + d, n - 1)) {
sum += a[i];
pq.emplace(a[i]);
while(sz(pq) + i > d) {
sum -= pq.top();
pq.pop();
}
res = max(res, sum);
}
return res;
}
struct Ayaya {
int ss, sb;
multiset<int> smol, big;
int l, r;
void init(int st) {
ss = sb = 0;
smol.clear();
big.clear();
l = st; r = st;
add(a[st]);
}
void add(int x) {
if(sz(big) && x >= *big.begin()) {
sb += x;
big.insert(x);
} else {
ss += x;
smol.insert(x);
}
}
void erase(int x) {
if(sz(big) && x >= *big.begin()) {
sb -= x;
big.erase(big.find(x));
} else {
ss -= x;
smol.erase(smol.find(x));
}
}
void update(int nl, int nr) {
while(l > nl) { l--; add(a[l]); }
while(l < nl) { erase(a[l]); l++; }
// cout << "owo!" << l << " " << r << " " << nl << " " << nr << " " << a[r] << "\n" << flush; out();
while(r > nr) { erase(a[r]); r--; }
while(r < nr) { r++; add(a[r]); }
}
int ask(int k) {
if(k <= 0) return 0;
if(k >= sz(big) + sz(smol)) return ss + sb;
while(sz(big) < k) {
int x = *prev(smol.end());
ss -= x; sb += x;
smol.erase(prev(smol.end()));
big.insert(x);
}
while(sz(big) > k) {
int x = *big.begin();
sb -= x; ss += x;
big.erase(big.begin());
smol.insert(x);
}
return sb;
}
void out() {
cout << ss << " " << sb << ":";
for(auto &i:smol) cout << " " << i;
for(auto &i:big) cout << " " << i;
cout << "\n" << flush;
}
} aya;
// divide & conquer
int dnc(int it, int ib, int jl, int jr, int st, int d) {
if(it > ib) return 0;
// cout << it << " " << ib << " " << jl << " " << jr << "\n" << flush;
int res = 0;
int im = (ib + it) / 2;
int mx = -1, mxj = -1;
For(j, jl, jr) {
// cout << aya.l << " " << aya.r << "\n" << flush;
aya.update(im, j);
int val = aya.ask(d - (st - im) * 2 - (j - st));
if(val > mx) {
mx = val; mxj = j;
}
}
res = mx;
// cout << mx << "\n" << flush;
res = max(mx, dnc(it, im - 1, mxj, jr, st, d));
res = max(mx, dnc(im + 1, ib, jl, mxj, st, d));
return res;
}
int solve2(int n, int st, int d) {
aya.init(st);
// return dnc(0, st, st, n - 1, st, d);
int res = 0;
For(l, 0, st) For(r, st, n - 1) {
aya.update(l, r);
res = max(res, aya.ask(d - (st - l) * 2 - (r - st)));
}
return res;
}
LL findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attractions[]) {
For(i, 0, n - 1) a[i] = attractions[i];
int res = 0;
For(phase, 0, 1) {
res = max(res, solve1(n, start, d));
res = max(res, solve2(n, start, d));
reverse(a, a + n);
start = n - 1 - start;
}
return res;
}
/*
60
4436
334588796671
3389595012736
*/
