#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 3e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;
pair<ll,int> a[N];
int p[N],num[4*N],S,n;
ll seg[4*N],d1[N],d2[N];
void update(int n,int s,int e,int in,bool to){
if(s > in || e < in)return;
if(s == e){
num[n] = to;
seg[n] = 1ll * to * a[in].first;
return;
}
update(n*2,s,(s+e)/2,in,to);
update(n*2+1,(s+e)/2+1,e,in,to);
num[n] = num[n*2] + num[n*2+1];
seg[n] = seg[n*2] + seg[n*2+1];
}
ll get(int n,int rem){
if(rem <= 0)return 0;
if(rem >= num[n])return seg[n];
return get(n*2,rem) + get(n*2+1,rem-num[2*n]);
}
void solve(int l,int r,int x,int y,int at,ll v[],int w){
if(l > r || x > y)return;
int cur = (l+r)/2;
at = -1;
v[cur] = -1;
for(int i=x;i<=y;i++){
update(1,1,n,p[i],1);
ll ans = get(1,cur - w * abs(i-S));
if(ans > v[cur]){
v[cur] = ans;
at = i;
}
}
for(int i=at;i<=y;i++)update(1,1,n,p[i],0);
solve(cur+1,r,at,y,-1,v,w);
for(int i=x;i<=y;i++)update(1,1,n,p[i],0);
solve(l,cur-1,x,at,-1,v,w);
}
void solve2(int l,int r,int x,int y,int at,ll v[],int w){
if(l > r || x > y)return;
int cur = (l+r)/2;
at = -1;
v[cur] = -1;
for(int i=y;i>=x;i--){
update(1,1,n,p[i],1);
ll ans = get(1,cur - w * abs(i-S));
if(ans > v[cur]){
v[cur] = ans;
at = i;
}
}
for(int i=x;i<=at;i++)update(1,1,n,p[i],0);
solve2(cur+1,r,x,at,at,v,w);
for(int i=x;i<=y;i++)update(1,1,n,p[i],0);
solve2(l,cur-1,at,y,at,v,w);
}
void clear(){
for(int i=1;i<=n;i++)update(1,1,n,p[i],0);
}
long long int findMaxAttraction(int N, int start, int d, int att[]){
S = start+1;
n = N;
for(int i=1;i<=n;i++)a[i] = {att[i-1],i};
sort(a+1,a+n+1);
reverse(a+1,a+n+1);
for(int i=1;i<=n;i++)p[a[i].second]=i;
ll ans = 0;
solve(1,d,S,n,-1,d1,2);
clear();
solve2(1,d,1,S-1,-1,d2,1);
clear();
for(int i=0;i<=d;i++)ans = max(ans,d1[i]+d2[d-i]);
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
solve(1,d,S+1,n,-1,d1,1);
clear();
solve2(1,d,1,S,-1,d2,2);
clear();
for(int i=0;i<=d;i++)ans = max(ans,d1[i]+d2[d-i]);
return ans;
cout << "WOW" << endl;
}
