#include <bits/stdc++.h>
/// 500 485 462 A4
typedef int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=1e5+100;
ll seg[2][N*4];
ll ja[N];
ll a[N];
ll dp[4][N];
ll n;
void upd(ll nod,ll l,ll r,ll id,ll di,ll val){
if (r-l==1){
seg[di][nod]+=val;
return ;
}
ll mid=(r+l)/2;
if (mid>id) upd(nod*2,l,mid,id,di,val);
else upd(nod*2+1,mid,r,id,di,val);
seg[di][nod]=seg[di][nod*2]+seg[di][nod*2+1];
}
ll get(ll nod,ll l,ll r,ll L,ll R,ll id){
if (l>=R || L>=r) return 0;
if (l>=L && r<=R) return seg[id][nod];
ll mid=(r+l)/2;
return get(nod*2,l,mid,L,R,id)+get(nod*2+1,mid,r,L,R,id);
}
ll where(ll nod,ll l,ll r,ll k){
if (r-l==1) return l;
ll mid=(r+l)/2;
if (seg[0][nod*2+1]>=k) return where(nod*2+1,mid,r,k);
else return where(nod*2,l,mid,k-seg[0][nod*2+1]);
}
void solve(ll l,ll r,ll L,ll R,ll id){
if (r<l) return ;
ll mid=(r+l)/2;
ll best=L,o=-1;
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
ll z=where(1,1,n+1,mid-i+1);
ll jav=get(1,1,n+1,z,n+1,1);
if (jav>o){
o=jav;
best=i;
}
}
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
dp[id][mid]=o;
solve(l,mid-1,L,best,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
}
solve(mid+1,r,best,R,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
}
void devide(ll l,ll r,ll L,ll R,ll id){
if (r<l) return ;
ll mid=(r+l)/2;
ll best=L,o=-1;
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
if (mid-i-i+2<0) continue;
ll z=where(1,1,n+1,mid-i-i+2);
ll jav=get(1,1,n+1,z,n+1,1);
if (jav>o){
o=jav;
best=i;
}
}
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
dp[id][mid]=o;
devide(l,mid-1,L,best,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
}
devide(mid+1,r,best,R,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
}
ll findMaxAttraction(int nn,int start,int d,int c[]){
vector <pii> b;
start++;
for (int i=1;i<=nn;i++){
a[i]=c[i-1];
}
for (int i=1;i<=nn;i++){
c[i]=a[i];
}
memset(a,0,sizeof a);
for (int i=1;i<=start;i++){
a[i]=c[i];
}
reverse(a+1,a+start+1);
for (int i=1;i<=start;i++){
b.pb({a[i],i});
}
sort(b.begin(),b.end());
for (int i=1;i<=b.size();i++){
ja[b[i-1].S]=i;
}
n=start;
solve(1,d,1,start,0);
// cout << " eih3 4w" << endl;
memset(seg,0,sizeof seg);
devide(1,d,1,start,1);
memset(seg,0,sizeof seg);
b.clear();
for (int i=start+1;i<=nn;i++){
a[i-start]=c[i];
}
n=nn-start;
for (int i=1;i<=n;i++){
b.pb({a[i],i});
}
sort(b.begin(),b.end());
for (int i=0;i<b.size();i++){
ja[b[i].S]=i+1;
}
solve(1,d,1,n,2);
memset(seg,0,sizeof seg);
devide(1,d,1,n,3);
ll ans=(dp[0][d]);
for (int i=0;i<=d-2;i++){
ans=max(ans,dp[0][i]+dp[3][d-i-2]);
}
for (int i=0;i<=d-1;i++){
ans=max(ans,dp[1][i]+dp[2][d-i-1]);
}
return ans;
}
/*
int c[5];
int32_t main(){
cin >> c[0] >> c[1] >> c[2] >> c[3] >> c[4];
cout << findMaxAttraction(5,2,7,c) << endl;
}
*/
/*
5
10 2 20 30 1
3 7
*/
