#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005
typedef long long lo;
int st,dist,n;
int dizi[lim];
lo cev;
int a[lim],val[lim];
lo tree[4*lim][2];// val_top - kac_tane
int cur_l=1,cur_r=1;
inline int cal(int x,int y){
int sol=abs(x-st);
int sag=abs(y-st);
return sol+sag+min(sol,sag);
}
inline void update(int node,int start,int end,int l,int r,lo val,int ekle){
if(start>end || start>r || end<l)return ;
if(start>=l && end<=r){
tree[node][0]+=ekle*val;
tree[node][1]+=ekle;
return ;
}
update(node*2,start,mid,l,r,val,ekle),update(node*2+1,mid+1,end,l,r,val,ekle);
tree[node][0]=tree[node*2][0]+tree[node*2+1][0];
tree[node][1]=tree[node*2][1]+tree[node*2+1][1];
}
inline void upd(int l,int r){
while(l<cur_l){
cur_l--;
update(1,1,n,a[cur_l],a[cur_l],val[a[cur_l]],1);
}
while(r>cur_r){
cur_r++;
update(1,1,n,a[cur_r],a[cur_r],val[a[cur_r]],1);
}
while(l>cur_l){
update(1,1,n,a[cur_l],a[cur_l],val[a[cur_l]],-1);
cur_l++;
}
while(r<cur_r){
update(1,1,n,a[cur_r],a[cur_r],val[a[cur_r]],-1);
cur_r--;
}
}
inline lo query(int node,int start,int end,int kalan){
if(start==end || kalan==0){
return tree[node][0];
}
int sag=tree[node*2+1][1];
if(sag>=kalan){// saga dallan
return query(node*2+1,mid+1,end,kalan);
}
else{
return tree[node*2+1][0]+query(node*2,start,mid,kalan-sag);
}
}
inline void dnq(int l,int r,int optl,int optr){
if(l>r)return ;
int mi=(l+r)/2;
int opt=optl;
lo best=-1;
for(int i=optl;i<=min(optr,mi);i++){
int git=cal(i,mi);
if(git>dist)continue;
int kalan=dist-git;
upd(i,mi);
lo cur_cev=0;
if(tree[1][1]<=kalan){
cur_cev=tree[1][0];
}
else{
cur_cev=query(1,1,n,kalan);
}
if(cur_cev>best){
best=cur_cev;
opt=i;
}
cev=max(cev,cur_cev);
}
dnq(l,mi-1,optl,opt),dnq(mi+1,r,opt,optr);
}
long long int findMaxAttraction(int nm, int start, int d, int attraction[]) {
st=start+1;
dist=d;
n=nm;
cev=0;
vector<pair<int,int>> v;
FOR{
dizi[i]=attraction[i-1];
v.pb({dizi[i],i});
}
sort(v.begin(),v.end());
for(int i=0;i<n;i++){
a[v[i].se]=i+1;
val[i+1]=v[i].fi;
}
update(1,1,n,a[1],a[1],val[a[1]],1);
dnq(st,n,1,st);
return cev;
}
//~ int main(){
//~ faster
//~ int n,start,d;
//~ cin>>n>>start>>d;
//~ int arr[n];
//~ FOR{
//~ cin>>arr[i-1];
//~ }
//~ lo cev=findMaxAttraction(n,start,d,arr);
//~ cout<<cev<<'\n';
//~ return 0;
//~ }
