//
// main.cpp
// holiday
//
// Created by Trần Nam Khánh on 11/21/20.
//
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int nax=1e5+1;
const int inf=1e9;
struct node
{
long long s;
int ac;
}seg[4*nax];
void build(int id,int l,int r)
{
seg[id].s=0;
seg[id].ac=0;
if(l==r)
{
return;
}
int mid=(l+r)>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int k,int val,int stat)
{
if(k<l||r<k)return;
if(l==r)
{
seg[id].ac=stat;
seg[id].s=val;
return;
}
int mid=(l+r)>>1;
update(id*2,l,mid,k,val,stat);
update(id*2+1,mid+1,r,k,val,stat);
seg[id].ac=seg[id*2].ac+seg[id*2+1].ac;
seg[id].s=seg[id*2].s+seg[id*2+1].s;
}
long long query(int id,int l,int r,int x)
{
long long res=0;
if(x<=0)return 0;
if(seg[id].ac<=x)
{
return seg[id].s;
}
int mid=(l+r)>>1;
res=query(id*2,l,mid,min(x,seg[id*2].ac))+query(id*2+1,mid+1,r,x-seg[id*2].ac);
return res;
}
int n,st,d,a[nax],pl[nax],attraction[nax];
long long dp[nax];
int ab(int a)
{
if(a<0)return -a;else return a;
}
void dc1(int lo,int hi,int lovl,int hivl)
{
if(lo>hi)return;
int mid=(lo+hi)>>1,x=lovl;
for(int i=mid;i<=st;i++)
{
update(1,1,n,pl[i],a[i],1);
}
for(int i=lovl;i<=hivl;i++)
{
int tmpd=d-min(ab(st-mid),ab(i-st))-ab(mid-i);
if(tmpd<0)break;
update(1,1,n,pl[i],a[i],1);
long long tmp=query(1,1,n,tmpd);
if(dp[mid]<tmp)
{
dp[mid]=tmp;
x=i;
}
}
for(int i=mid;i<=st;i++)
{
update(1,1,n,pl[i],0,0);
}
for(int i=x;i<=hivl;i++)update(1,1,n,pl[i],0,0);
dc1(mid+1,hi,x,hivl);
for(int i=lovl;i<=x;i++)update(1,1,n,pl[i],0,0);
dc1(lo,mid-1,lovl,x);
}
long long findMaxAttraction(int N, int start, int days, int attraction[])
{
long long ans=0;
pair<int,int>b[nax];
n=N;st=start;d=days;
for(int i=1;i<=n;i++)
{
a[i]=attraction[i-1];
b[i].first=-a[i];
b[i].second=i;
dp[i]=-inf;
}
build(1,1,n);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
{
pl[b[i].second]=i;
}
dc1(1,st,st+1,n);
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
return ans;
}
