#include"holiday.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;
ll ans; // :))
int n, start, D, k, u, v, x, y, t, a, b;
int A[MAXN];
struct Set{
ll sum, sz;
int mark[MAXN];
priority_queue<pii, vector<pii>, greater<pii>> X;
priority_queue<pii> Y;
inline void relax(){
while (X.size() && mark[X.top().second]!=1) X.pop();
while (Y.size() && mark[Y.top().second]!=2) Y.pop();
}
void Add(int i){
relax();
int y=-inf, x=inf;
if (X.size()) x=X.top().first;
if (Y.size()) y=Y.top().first;
if (A[i]<=x) mark[i]=2, Y.push({A[i], i});
else mark[i]=1, X.push({A[i], i}), sum+=A[i], sz++;
}
void Rem(int i){
if (mark[i]==1) sum-=A[i], sz--;
mark[i]=0;
relax(); // not necessary
}
ll Get(int k){
if (k<0) return -INF;
while (sz<k && Y.size()){
int i=Y.top().second;
Y.pop();
if (mark[i]!=2) continue ;
mark[i]=1;
X.push({A[i], i});
sum+=A[i];
sz++;
}
while (sz>k){
int i=X.top().second;
X.pop();
if (mark[i]!=1) continue ;
mark[i]=2;
Y.push({A[i], i});
sum-=A[i];
sz--;
}
return sum;
}
} S;
ll findMaxAttraction(int nn, int starttt, int d, int attraction[]){
n=nn;
D=d;
start=starttt;
for (int i=0; i<n; i++) A[i]=attraction[i];
for (int i=start; ~i; i--){
S.Add(i);
ans=max(ans, S.Get(D-(start-i)));
for (int j=start+1; j<n; j++){
S.Add(j);
int a=start-i, b=j-start;
ans=max(ans, S.Get(D-(a+b+min(a, b))));
}
for (int j=start+1; j<n; j++) S.Rem(j);
}
return ans;
}
