#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pb push_back
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int MX = 100005;
int ans = 0,N,D,S;
pii a[MX];
struct node{
int cnt,sum;
node(){
cnt = 0;
sum = 0;
}
} seg[4*MX];
void upd(int ind,int l,int r,int pos,int val,int type){
if(pos < l or pos > r) return;
if(l == r){
seg[ind].cnt = type;
seg[ind].sum = val*type;
// trace(ind,l,r,pos,val,type,seg[ind].cnt,seg[ind].sum);
return;
}
int m = (l+r)/2;
upd(2*ind,l,m,pos,val,type);
upd(2*ind+1,m+1,r,pos,val,type);
seg[ind].cnt = seg[2*ind].cnt+seg[2*ind+1].cnt;
seg[ind].sum = seg[2*ind].sum+seg[2*ind+1].sum;
// trace(ind,l,r,pos,val,type,seg[ind].cnt,seg[ind].sum);
}
int quer(int ind,int l,int r,int rem){
// trace(ind,l,r,rem);
if(l == r){
if(rem) return seg[ind].sum;
else return 0;
}
int m = (l+r)/2;
if(seg[2*ind+1].cnt >= rem) return quer(2*ind+1,m+1,r,rem);
else return seg[2*ind+1].sum+quer(2*ind,l,m,rem-seg[2*ind+1].cnt);
}
void solve(int l,int r,int optl,int optr){
// assumes r+1...optl-1 are already activated in segtree
// trace(l,r,optl,optr);
int mid = (l+r)/2;
if(S-mid >= D){
if(mid != r) solve(mid+1,r,optl,optr);
return;
}
int cur = -1,opt = optl;
FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,1);
// trace(l,r,optl,optr);
FOR(i,optl,optr+1){
upd(1,0,N-1,a[i].S,a[i].F,1);
int rem = D-2*min(S-mid,i-S)-max(S-mid,i-S);
if(rem <= 0) break;
int gg = quer(1,0,N-1,rem);
// trace(mid,i,rem,gg);
if(gg > cur){
cur = gg;
opt = i;
}
}
if(cur > ans) ans = cur;
FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,0);
FOR(i,optl,optr+1) upd(1,0,N-1,a[i].S,a[i].F,0);
if(l != mid){
FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,1);
solve(l,mid-1,optl,opt);
FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,0);
}
if(r != mid){
FOR(i,optl,opt) upd(1,0,N-1,a[i].S,a[i].F,1);
solve(mid+1,r,opt,optr);
FOR(i,optl,opt) upd(1,0,N-1,a[i].S,a[i].F,0);
}
}
int findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
vector<pii> v;
D = d;
N = d;
S = start;
REP(i,n) v.pb({attraction[i],i});
sort(v.begin(),v.end());
REP(i,n) a[v[i].S] = {v[i].F,i};
// REP(i,n){
// trace(i,a[i].F,a[i].S);
// }
solve(0,start,start,n-1);
return ans;
}
