#include "holiday.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define INF (1LL<<60)
#define _1 first
#define _2 second
int N, D;
int A[100000];
long long dpL[300000], dpR[300000];
inline long long top_sum_less_than(priority_queue<P> &erased, int r, int lim) {
vector<int> backup;
long long s = 0;
while (!erased.empty() && backup.size() < lim) {
int x = erased.top()._2;
erased.pop();
if (x >= r) continue;
backup.pb(x);
s += A[x];
}
for (int x : backup) erased.push(P(A[x], x));
return s;
}
inline long long top_sum_greater_than(priority_queue<P> &erased, int l, int lim) {
vector<int> backup;
long long s = 0;
while (!erased.empty() && backup.size() < lim) {
int x = erased.top()._2;
erased.pop();
if (x <= l) continue;
backup.pb(x);
s += A[x];
}
for (int x : backup) erased.push(P(A[x], x));
return s;
}
long long solve(int start) {
rep(i, D+1) dpL[i] = dpR[i] = 0;
if (start < N-1) {
int r = N-1;
long long s = 0;
set<P> pq;
priority_queue<P> erased;
for (int x=start+1; x<N; x++) s += A[x], pq.insert(P(A[x], x));
for (int d=(N-1-start)*2; d>=0; d--) {
bool bad = false;
while (!pq.empty() && r-start+pq.size() > d) {
int x = pq.begin()->_2;
if (x == r) {
bad = true;
break;
}
erased.push(P(A[x], x));
s -= A[x];
pq.erase(pq.begin());
}
long long e = 0;
if (!bad) e = top_sum_less_than(erased, r, 2);
if (bad || e > A[r]) {
s -= A[r];
pq.erase(P(A[r], r));
r--;
}
while (!erased.empty() && r-start+pq.size() < d) {
int x = erased.top()._2;
erased.pop();
pq.insert(P(A[x], x));
s += A[x];
}
if (d <= D) dpR[d] = s;
}
}
if (start > 0) {
int l = 0;
long long s = 0;
set<P> pq;
priority_queue<P> erased;
for (int x=0; x<start; x++) s += A[x], pq.insert(P(A[x], x));
for (int d=start*3; d>=0; d--) {
bool bad = false;
while (!pq.empty() && (start-l)*2+pq.size() > d) {
int x = pq.begin()->_2;
if (x == l) {
bad = true;
break;
}
erased.push(P(A[x], x));
s -= A[x];
pq.erase(pq.begin());
}
long long e = 0;
if (!bad) e = top_sum_greater_than(erased, l, 3);
if (bad || e > A[l]) {
s -= A[l];
pq.erase(P(A[l], l));
l++;
}
while (!erased.empty() && (start-l)*2+pq.size() < d) {
int x = erased.top()._2;
erased.pop();
pq.insert(P(A[x], x));
s += A[x];
}
if (d <= D) dpL[d] = s;
}
}
long long m = 0;
rep(l, D+1) {
m = max(m, dpL[l] + dpR[D-l]);
if (D-l-1>0) m = max(m, dpL[l] + dpR[D-l-1] + A[start]);
}
return m;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n, D = d;
rep(i, N) A[i] = attraction[i];
long long m = 0;
m = max(m, solve(start));
reverse(A, A+N);
m = max(m, solve(N-1-start));
return m;
}
