#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+5;
const ll offset=1e9;
const ll blk=317;
const ll inf=1e18;
const int base =311;
const ll mod=1e9+7;
int n,s,d;
int a[maxn];
mt19937 rng(250111);
int res=0;
namespace sub2
{
void solve()
{
priority_queue<int,vector<int>,greater<int>> pq;
int ans=0,res=0;
for1(i,1,n)
{
int left=d-i+1;
if (left<0) break;
pq.push(a[i]);
ans+=a[i];
while (pq.size()>left)
{
ans-=pq.top();
pq.pop();
}
res=max(res,ans);
}
}
}
namespace sub13
{
int b[maxn];
void chk(int j)
{
priority_queue<int,vector<int>,greater<int>> pq;
int ans=0;
for1(i,j,n)
{
int left=d-(s-j)-i+j;
if (left<0) break;
pq.push(a[i]);
ans+=a[i];
while (pq.size()>left)
{
ans-=pq.top();
pq.pop();
}
res=max(res,ans);
}
}
void solve()
{
for1(j,1,s)
{
chk(j);
}
for1(i,1,n) b[i]=a[n-i+1];
s=n-s+1;
for1(i,1,n) a[i]=b[i];
for1(j,1,s)
{
chk(j);
}
}
}
namespace sub4
{
int b[maxn];
void chk(int j)
{
priority_queue<int,vector<int>,greater<int>> pq;
int ans=0;
for1(i,j,n)
{
int left=d-(s-j)-i+j;
if (left<0) break;
pq.push(a[i]);
ans+=a[i];
while (pq.size()>left)
{
ans-=pq.top();
pq.pop();
}
res=max(res,ans);
}
}
void solve()
{
for1(j,1,min(20LL,s)) chk(j);
for1(j,max(1LL,s-20LL),s) chk(j);
for1(i,1LL,50)
{
int j=rng()%s+1LL;
chk(abs(j));
}
for1(i,1LL,n) b[i]=a[n-i+1LL];
s=n-s+1LL;
for1(i,1LL,n) a[i]=b[i];
for1(j,1LL,min(20LL,s)) chk(j);
for1(j,max(1LL,s-20LL),s) chk(j);
for1(i,1LL,50)
{
int j=rng()%s+1LL;
chk(abs(j));
}
}
}
ll findMaxAttraction(int32_t nn, int32_t start, int32_t dd,int32_t attraction[])
{
s=start+1;
n=nn;
d=dd;
for1(i,1,n)
{
a[i]=attraction[i-1];
}
if (s==1)
{
sub2::solve();
return res;
}
if (n<=1000)
{
sub13::solve();
return res;
}
sub4::solve();
return res;
}
/*
5 0 6
10 2 20 30 1
*/
