#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int ch[100001],n,s,d,a[100001];
long long calc(int k){
for (int i=0;i<n;i++)
ch[i]=0;
int r=min(d+s-k,n-1),l=max((s+r-d+k+1)/2,0),cnt=0,dist=s+r-l*2;
long long val=0,mx=0;
priority_queue <pair <int, int>> q;
for (int i=l;i<=r;i++)
q.push({a[i],i});
while (!q.empty()&&cnt<k){
ch[q.top().second]=1;
val+=q.top().first;
q.pop();
cnt++;
}
mx=val;
for (int i=l-1;i>=0;i--){
dist+=2;
while (dist+k>d){
cnt-=ch[r];
val-=ch[r]*a[r];
r--;
dist--;
}
if (r-l+1<k)
break;
q.push({a[i],i});
while (!q.empty()&&cnt<k){
ch[q.top().second]=1;
val+=q.top().first;
q.pop();
cnt++;
}
mx=max(mx,val);
}
return mx;
}
long long solve(){
int pos=0;
long long mx=0,kq=0;
for (int i=0;i<n;i+=300){
long long val=calc(i);
if (val>mx){
mx=val;
pos=i;
}
}
for (int i=max(pos-300,0);i<min(pos+300,n);i++)
kq=max(kq,calc(i));
return kq;
}
long long findMaxAttraction(int N, int start, int D, int attraction[]){
n=N;
s=start;
d=D;
for (int i=0;i<n;i++)
a[i]=attraction[i];
long long res=solve();
reverse(a,a+n);
s=n-s-1;
return max(res,solve());
}
