#include "holiday.h"
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pp;
typedef priority_queue<pp> pq;
int st;
ll a[100000];
ll b[100000];
bool chk[100000];
void f(int j,int i,int cnt){
pq Q;
for(int k=j;k<=i;k++){
Q.push(pp(a[k],k));
}
ll sum=0,base=0;
while(!Q.empty()){
int v=Q.top().second;Q.pop();
if(v<j)continue;
if(cnt==0){
cnt+=2;
if(chk[j])chk[j]=0,base+=a[j];
j++;
if(j>st)break;
}
sum+=a[v];
chk[v]=1;
cnt--;
b[i]=max(b[i],sum-base);
}
}
void f2(int j,int i,int cnt){
pq Q;
for(int k=i;k<=j;k++){
Q.push(pp(a[k],k));
}
ll sum=0,base=0;
while(!Q.empty()){
int v=Q.top().second;Q.pop();
if(j<v)continue;
if(cnt==0){
cnt+=2;
if(chk[j])chk[j]=0,base+=a[j];
j--;
if(j<st)break;
}
sum+=a[v];
chk[v]=1;
cnt--;
b[i]=max(b[i],sum-base);
}
}
ll findMaxAttraction(int n, int start, int d, int attraction[]){
st=start;
for(int i=0;i<n;i++){
a[i]=attraction[i];
}
for(int i=start;i<n;i++){
int x=i-start;
int j=max(0,start-(d-x)/2);
int y=start-j;
int cnt=d-x-2*y;
f(j,i,cnt);
}
for(int i=start;i>=0;i--){
int x=start-i;
int j=min(n-1,start+(d-x)/2);
int y=j-start;
int cnt=d-x-2*y;
f2(j,i,cnt);
}
ll ans=0;
for(int i=0;i<n;i++)ans=max(ans,b[i]);
return ans;
}
