#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define ll long long
#define N 100005
#define orta ((bas+son)>>1)
int Left,Right,n,d,totD,start;
int pos[N];
ll dp[N];
pair<ll,int> attr[N];
struct SEG {
int ok;
ll sum;
}S[N*4];
SEG merge(SEG A,SEG B) {
return {A.ok+B.ok,A.sum+B.sum};
}
ll get(int node,int bas,int son,int val) {
if(bas==son) return (val>0)*S[node].sum;
if(S[node*2].ok>val) return get(node*2,bas,orta,val);
else return get(node*2+1,orta+1,son,val-S[node*2].ok)+S[node*2].sum;
}
void up(int node,int bas,int son,int x,int val) {
if(bas>x || son<x) return ;
if(bas==x && son==x) {
S[node].ok=val;
S[node].sum=val*attr[bas].st;
return ;
}
up(node*2,bas,orta,x,val);
up(node*2+1,orta+1,son,x,val);
S[node]=merge(S[node*2],S[node*2+1]);
}
void up_it() {
totD=Right-Left+min(start-Left,Right-start);
}
void moveR(int val) {
while(Right<val) {
Right++;
up(1,0,n-1,pos[Right],1);
}
while(Right>val) {
up(1,0,n-1,pos[Right],0);
Right--;
}
up_it();
}
void moveL(int val) {
while(Left<val) {
up(1,0,n-1,pos[Left],0);
Left++;
}
while(Left>val) {
Left--;
up(1,0,n-1,pos[Left],1);
}
up_it();
}
void solve(int bas,int son,int pbas,int pson) {
if(bas>son) return ;
moveL(orta);
int tutP=pbas;
ll ans=-1;
for(int i=pbas;i<=pson;i++) {
moveR(i);
if(totD>d) break ;
int rem=d-totD;
ll res=get(1,0,n-1,min(rem,S[1].ok));
if(res>=ans) {
ans=res;
tutP=i;
}
}
dp[orta]=ans;
solve(bas,orta-1,pbas,tutP);
solve(orta+1,son,tutP,pson);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
ll ans=0;
::n=n;
::d=d;
::start=start;
for(int i=0;i<n;i++) attr[i]={attraction[i],i};
sort(attr,attr+n,greater< pair<ll,int> >());
for(int i=0;i<n;i++) pos[attr[i].nd]=i;
Right=start-1;
Left=start+1;
solve(0,start,start,n-1);
for(int i=0;i<=start;i++) ans=max(ans,dp[i]);
return ans;
}
