#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
long long lt[d+1][2], rt[d+1][2];
FOR(m,1,2) {
priority_queue<int,vector<int>,greater<int>> incl;
priority_queue<int> excl;
int cleared = -1;
int processed = start+1;
long long sum = 0;
queue<tuple<int,int,int,int,int>> q;
q.emplace(0,0,d,0,start);
while (!q.empty()) {
int dep,s,e,l,r; tie(dep,s,e,l,r) = q.front(); q.pop();
//cout << "processing " << s << " " << e << " " << l << " " << r << endl;
int mid = (s+e)/2;
if (dep > cleared) {
while (!incl.empty()) incl.pop();
while (!excl.empty()) excl.pop();
processed = start+1;
sum = 0;
//cout << "cleared " << endl;
}
while (processed > r) {
sum += attraction[--processed]; incl.push(attraction[processed]);
}
while (!excl.empty() && SZ(incl)+(start-r)*m < mid) {
sum += excl.top();
incl.push(excl.top());
excl.pop();
}
//cout << "INCL " << SZ(incl) << " EXCL " << SZ(excl) << endl;
lt[mid][m-1] = 0;
int idx = r;
RFOR(i,r,l){
if (i < processed) {
sum += attraction[i]; incl.push(attraction[i]);
processed = i;
}
while (!incl.empty() && SZ(incl)+(start-i)*m > mid) {
sum -= incl.top();
excl.push(incl.top());
incl.pop();
}
if (sum > lt[mid][m-1]) lt[mid][m-1] = sum, idx = i;
}
//cout << "\tmid " << mid << " best " << lt[mid][m-1] << " at " << idx << endl;
if (s < mid) q.emplace(dep+1,s,mid-1,idx,r);
if (mid < e) q.emplace(dep+1,mid+1,e,l,idx);
}
}
FOR(m,1,2) {
priority_queue<int,vector<int>,greater<int>> incl;
priority_queue<int> excl;
int cleared = -1;
int processed = start;
long long sum = 0;
queue<tuple<int,int,int,int,int>> q;
q.emplace(0,0,d,start+1,n-1);
while (!q.empty()) {
int dep,s,e,l,r; tie(dep,s,e,l,r) = q.front(); q.pop();
//if (m == 1) cout << "processing " << s << " " << e << " " << l << " " << r << endl;
int mid = (s+e)/2;
if (dep > cleared) {
while (!incl.empty()) incl.pop();
while (!excl.empty()) excl.pop();
processed = start;
sum = 0;
cleared = dep;
//if (m == 1) cout << "cleared " << endl;
}
while (processed < l) {
sum += attraction[++processed]; incl.push(attraction[processed]);
}
while (!excl.empty() && SZ(incl)+(l-start)*m < mid) {
sum += excl.top();
incl.push(excl.top());
excl.pop();
}
//if (m == 1) cout << processed << " INCL " << SZ(incl) << " EXCL " << SZ(excl) << " :: " << SZ(incl)+(l-start)*m << endl;
rt[mid][m-1] = 0;
int idx = l;
FOR(i,l,r){
if (i > processed) {
sum += attraction[i]; incl.push(attraction[i]);
processed = i;
}
while (!incl.empty() && SZ(incl)+(i-start)*m > mid) {
sum -= incl.top();
excl.push(incl.top());
incl.pop();
}
if (sum > rt[mid][m-1]) rt[mid][m-1] = sum, idx = i;
}
//if (m == 1) cout << "\tmid " << mid << " best " << rt[mid][m-1] << " at " << idx << endl;
if (s < mid) q.emplace(dep+1,s,mid-1,l,idx);
if (mid < e) q.emplace(dep+1,mid+1,e,idx,r);
}
}
long long ans = 0;
FOR(x,0,d){
//cout << x << " :: " << lt[x][0] << ' ' << lt[x][1] << ' ' << rt[x][0] << ' ' << rt[x][1] << endl;
ans = max({ans,lt[x][0]+rt[d-x][1],lt[x][1]+rt[d-x][0]});
}
return ans;
}
