/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include "holiday.h"
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define pb push_back
#define pf push_front
#define endl "\n"
#define fil(arr,x) memset(arr,x,sizeof(arr))
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
return (max(a,b)/__gcd(a,b))*min(a,b);
}
vector<ll>vec;
ll val[500005];
struct segtree{
vector<ll>tree;
vector<ll>cnt;
int size;
void init(int n){
size=n;
tree.assign(n*4+5,0LL);
cnt.assign(n*4+5,0LL);
}
void insert(int l,int r,int p,int i){
if(l==r){
tree[p]+=val[i];
cnt[p]++;
return;
}
int mid=(l+r)/2;
if(i>mid) insert(mid+1,r,p*2+1,i);
else insert(l,mid,p*2,i);
tree[p]=tree[p*2]+tree[p*2+1];
cnt[p]=cnt[p*2]+cnt[p*2+1];
}
void insert(int i){
insert(1,size,1,i);
}
void erase(int l,int r,int p,int i){
if(l==r){
tree[p]-=val[i];
cnt[p]--;
return;
}
int mid=(l+r)/2;
if(i>mid) erase(mid+1,r,p*2+1,i);
else erase(l,mid,p*2,i);
tree[p]=tree[p*2]+tree[p*2+1];
cnt[p]=cnt[p*2]+cnt[p*2+1];
}
void erase(int i){
erase(1,size,1,i);
}
ll query(int l,int r,int p,int k){
if(l>r)return 0LL;
if(l==r){
return min(k,cnt[p]) * 1LL * val[l];
}
int mid=(l+r)/2;
if (cnt[p]<=k)return tree[p];
else if (cnt[p*2+1]>k)return query(mid+1,r,p*2+1,k);
else return query(l,mid,p*2,k-cnt[p*2+1]) + tree[p*2+1];
}
ll maxk(int k){
if (k<=0)return 0LL;
return query(1,size,1,k);
}
}sg;
int L=0,R=0;
void update(int l,int r) {
while (R<r)sg.insert(vec[++R]);
while (L>l)sg.insert(vec[--L]);
while (R>r)sg.erase(vec[R--]);
while (L<l)sg.erase(vec[L++]);
}
ll dp[500005];
void solve(int l,int r,int optl,int optr,int d,int s) {
if (l>r)return;
int mid=l+r>>1;
int opt=optl;
for (int j=optl;j<=optr;j++) {
int x=min(s-j,mid-s) + (mid-j);
update(j,mid);
ll ans=sg.maxk(d-x);
if (ans>dp[mid])
dp[mid]=ans,opt=j;
}
solve(l,mid-1,optl,optr,d,s);
solve(mid+1,r,optl,optr,d,s);
}
long long findMaxAttraction(int n,int s,int d,int a[]) {
/*
* x=min(r-s,s-l) + (r-l)
* dp[l][r] = max(l,r,d-x)
*/
set<int>st;
for (int i=0;i<n;i++)vec.push_back(a[i]),st.insert(a[i]);
int cnt=1;
map<int,int>mp;
for (auto i:st)
mp[i]=cnt,val[cnt++]=i;
for (auto &i:vec)i=mp[i];
sg.init(n);
sg.insert(vec[0]);
solve(s,n-1,0,s,d,s);
ll ans=0;
for (int i=s;i<n;i++)
ans=max(ans,dp[i]);
return ans;
}
