#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pii=pair<lint,int>;
const int lim=1e5+100;
int n,s,d,a[lim];
lint ans=0;
struct treap{
struct Node{
int val;
lint sum;
int pri,cnt;
Node*l,*r;
Node(int val):val(val),sum(val),pri(rand()),cnt(1),l(0),r(0){}
};
using pnode=Node*;
inline int getcnt(const pnode&p){
if(p)return p->cnt;
return 0;
}
inline lint getsum(const pnode&p){
if(p)return p->sum;
return 0;
}
inline void updcnt(pnode p){
if(p){
p->cnt=1+getcnt(p->l)+getcnt(p->r);
p->sum=p->val+getsum(p->l)+getsum(p->r);
}
}
inline void split(pnode p,pnode&l,pnode&r,int val){
if(!p){
l=r=0;
return;
}
if(val<=p->val){
split(p->l,l,p->l,val);
r=p;
}else{
split(p->r,p->r,r,val);
l=p;
}
updcnt(p);
}
inline void merge(pnode&p,pnode l,pnode r){
if(!l){
p=r;
return;
}
if(!r){
p=l;
return;
}
if(l->pri<r->pri){
merge(r->l,l,r->l);
p=r;
}else{
merge(l->r,l->r,r);
p=l;
}
updcnt(p);
}
pnode root=0;
inline void insert(pnode&p,pnode t){
if(!p){
p=t;
return;
}
if(t->pri<p->pri){
if(p->val<t->val){
insert(p->r,t);
}else{
insert(p->l,t);
}
}else{
split(p,t->l,t->r,t->val);
p=t;
}
updcnt(p);
}
inline void insert(int val){
pnode t=new Node(val);
insert(root,t);
}
pnode tt1,tt2;
inline void erase(pnode&p,int val){
if(!p)return;
if(p->val==val){
tt1=p->l,tt2=p->r;
delete p;
merge(p,tt1,tt2);
}else if(val<p->val){
erase(p->l,val);
}else{
erase(p->r,val);
}
updcnt(p);
}
inline void erase(int val){
erase(root,val);
}
inline lint query(pnode p,int k){
if(!p||k<=0)return 0;
if(1+getcnt(p->r)<=k){
return getsum(p->r)+p->val+query(p->l,k-1-getcnt(p->r));
}
return query(p->r,k);
}
inline lint query(int k){
return query(root,k);
}
inline void clear(pnode p){
if(!p)return;
clear(p->l);
delete p;
clear(p->r);
}
inline void clear(){
clear(root);
root=0;
}
void debug(pnode p){
if(!p)return;
debug(p->l);
cerr<<p->val<<" ";
debug(p->r);
}
void debug(){
cerr<<"debug :: ";
debug(root);
cerr<<" :: end of debug\n";
}
}tr;
int L,R;
int startopt,endopt,inc;
lint best,canmake;
void dnc(int l,int r,int optl,int optr,bool ty=0){
if(r<l)return;
#define mid (l+r>>1)
if(!ty){
startopt=optr;
endopt=optl;
inc=-1;
}else{
startopt=optl;
endopt=optr;
inc=1;
}
while(R<mid){
tr.insert(a[++R]);
}
while(startopt<L){
tr.insert(a[--L]);
}
while(mid<R){
tr.erase(a[R--]);
}
while(L<startopt){
tr.erase(a[L++]);
}
#define movesleft(idx) (d-2*(s-(idx))-(mid-s))
int opt=startopt;
best=tr.query(movesleft(opt));
ans=max(ans,best);
for(int i=startopt+inc;(startopt<=i&&i<=endopt)||(endopt<=i&&i<=startopt);i+=inc){
if(inc==-1)tr.insert(a[i]);
else tr.erase(a[i-1]);
L+=inc;
canmake=tr.query(movesleft(i));
if(best<canmake){
opt=i;
best=canmake;
ans=max(ans,best);
}
}
if(!ty){
dnc(l,mid-1,optl,opt,1);
dnc(mid+1,r,opt,optr,1);
}else{
dnc(mid+1,r,opt,optr);
dnc(l,mid-1,optl,opt);
}
}
lint findMaxAttraction(int N, int S, int D, int attraction[]) {
n=N,s=S,d=D;
for(int i=0;i<n;i++)a[i]=attraction[i];
L=s,R=s-1;
dnc(s,n-1,0,s);
for(int i=0;i<n-i-1;i++){
swap(a[i],a[n-i-1]);
}
tr.clear();
L=s,R=s-1;
s=n-s-1;
dnc(s,n-1,0,s);
return ans;
}
