#include"holiday.h"
#include "bits/stdc++.h"
#define here cerr<<"======================\n"
#define fi first
#define sc second
#define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;}
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
const ll maxn = 300005;
ll n;
ll a[maxn];
ll d;
ll st;
ll opt[maxn];
pll t[2*maxn];
ll ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
ll id[maxn];
pll b[maxn];
void init(ll &v,ll tl,ll tr) {
if(!v) v = ++tsz;
if(tl==tr){t[v] = {0,0};return;}
ll mid = (tl+tr)/2;
init(ls[v],tl,mid);
init(rs[v],mid+1,tr);
t[v] = {0,0};
}
ll get(ll v,ll tl,ll tr,ll k) {
if(k==0) return 0;
if(k>=t[v].sc) return t[v].fi;
ll mid = (tl+tr)/2;
if(k>=t[rs[v]].sc) return t[rs[v]].fi + get(ls[v],tl,mid,k-t[rs[v]].sc);
return get(rs[v],mid+1,tr,k);
}
void upd(ll v,ll tl,ll tr,ll i,bool e) {
if(v==root){i = id[i];}
if(tl==tr) {
if(e) t[v] = {b[i].fi,1};
else t[v] = {0,0};
return;
}
ll mid = (tl+tr)/2;
if(i<=mid) upd(ls[v],tl,mid,i,e);
else upd(rs[v],mid+1,tr,i,e);
t[v] = {t[ls[v]].fi+t[rs[v]].fi,t[ls[v]].sc+t[rs[v]].sc};
}
ll cr;
ll dpr[maxn];
ll dpl[maxn];
bool bf = 0;
void dp(ll l,ll r,ll tl,ll tr) {
if(l>r) return;
ll mid = (l+r)/2;
if(bf) tl = st,tr = n;
while(cr>tl) {
upd(root,1,n,cr,0);
cr--;
}
while(cr<tl) {
upd(root,1,n,cr+1,1);
cr++;
}
opt[mid] = -1;
dpr[mid] = -1;
for(ll i = tl;i<=tr;i++) {
ll ck = mid-2*(i-st);
if(ck<0) break;
ll cur = get(root,1,n,ck);
if(cur>dpr[mid]) {
dpr[mid] = cur;
opt[mid] = i;
}
if(i<n) {
upd(root,1,n,i+1,1);
cr = i+1;
}
}
if(opt[mid]!=-1) {
dp(l,mid-1,tl,opt[mid]);
dp(mid+1,r,opt[mid],tr);
}else {
dp(l,mid-1,tl,tr);
dp(mid+1,r,tl,tr);
}
dpr[mid] = max(dpr[mid],0LL);
}
void dp2(ll l,ll r,ll tl,ll tr) {
if(l>r) return;
ll mid = (l+r)/2;
if(bf) tl = 1,tr = st-1;
while(cr<tr) {
upd(root,1,n,cr,0);
cr++;
}
while(cr>tr) {
upd(root,1,n,cr-1,1);
cr--;
}
opt[mid] = -1;
dpl[mid] = -1;
for(ll i = tr;i>=tl;i--) {
ll ck = mid-(st-i);
if(ck<0) continue;
ll cur = get(root,1,n,ck);
if(cur>dpl[mid]) {
dpl[mid] = cur;
opt[mid] = i;
}
if(i>1) {
upd(root,1,n,i-1,1);
cr = i-1;
}
}
if(opt[mid]!=-1) {
dp2(mid+1,r,tl,opt[mid]);
dp2(l,mid-1,opt[mid],tr);
}else {
dp2(mid+1,r,tl,tr);
dp2(l,mid-1,tl,tr);
}
dpl[mid] = max(dpl[mid],0LL);
}
ll reshi() {
for(ll i = 1;i<=n;i++) b[i] = {a[i],i};
sort(b+1,b+1+n);
for(ll i = 1;i<=n;i++) id[b[i].sc] = i;
init(root,1,n);
cr = st;
upd(root,1,n,st,1);
for(ll i = 0;i<=d;i++) dpr[i] = dpl[i] = opt[i] = 0;
dp(1,d,st,n);
for(ll i = 0;i<=d;i++) dpl[i] = opt[i] = 0;
init(root,1,n);
cr = st-1;
if(cr) upd(root,1,n,cr,1);
dp2(2,d,1,st-1);
ll ans = 0;
dpl[0] = dpl[1] = dpr[0] = 0;
//ceri(dpl,0,d);
for(ll i = 0;i<=d;i++) ans = max(ans,dpl[i]+dpr[d-i]);
return ans;
}
ll findMaxAttraction(int N, int str, int D, int attraction[]) {
n = N,d = D,st = str+1;
for(ll i = 1;i<=n;i++) a[i] = attraction[i-1];
ll ans = reshi();
reverse(a+1,a+1+n);
st = n-st+1;
ans = max(ans,reshi());
return ans;
}
