#include"holiday.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define f first
#define s second
const int N=100000;
ll ans;
int A[N];
int n, d;
int cnt[4*N];
int pos[N];
ll sum[4*N];
// ------------Segtree------------------
void upd(int i, int v, int x, int lx, int rx){
if(rx-lx==1){
cnt[x]=(v>0);
sum[x]=v;
return;
}
int m=(lx+rx)/2;
if(i<m) upd(i, v, 2*x+1, lx, m);
else upd(i, v, 2*x+2, m, rx);
sum[x]=sum[2*x+1]+sum[2*x+2];
cnt[x]=cnt[2*x+1]+cnt[2*x+2];
}
void upd(int i, int v){ upd(i, v, 0, 0, n); }
ll walk(int k, int x, int lx, int rx){
if(k>=cnt[x]) return sum[x];
if(k<=0) return 0;
int m=(lx+rx)/2;
if(cnt[2*x+2]<=k) return sum[2*x+2]+walk(k-cnt[2*x+2], 2*x+1, lx, m);
else return walk(k, 2*x+2, m, rx);
}
ll walk(int k) { return walk(k, 0, 0, n); }
// ----------------END -------------------
void solve(int l, int r, int a, int b, int start){
if(r<=l || b<a) return;
// cout << "solve " << l << " " << r << " " << a << " " << b << " " << start << "\n";
int m=(l+r)/2;
rep(i,l,m) upd(pos[i], A[i]);
pair<ll, int> opt;
for(int i=b; i>=a; i--){
if(i!=l) upd(pos[i], A[i]);
int dist=m-i+m-start;
ll w=walk(d-dist);
opt=max(opt, {w, i});
}
// cout << m << " " << a << " "<< b << " opt " << opt.f << " " << opt.s << "\n";
// opt.s*=-1; // ??
ans=max(ans, opt.f);
rep(i,l,m) upd(pos[i], 0);
for(int i=b; i>=a; i--) if(i!=l) upd(pos[i], 0);
rep(i,opt.s+1,b) upd(pos[i], A[i]);
solve(l, m, a, opt.s, start);
rep(i,l,m) upd(pos[i], A[i]);
rep(i,opt.s+1,b) upd(pos[i], 0);
solve(m+1, r, opt.s, b, start);
rep(i,l,m) upd(pos[i], 0);
}
void go(int start){
solve(start, n, 0, start, start);
}
void line(int start){
rep(i,start,n-1){
upd(pos[i], A[i]);
// cout << i << " " << walk(d-(i-start)) << "\n";
ans=max(ans, walk(d-(i-start)));
}
rep(i,start,n-1){
upd(pos[i], 0);
}
for(int i=start; i>=0; i--){
upd(pos[i], A[i]);
ans=max(ans, walk(d-(start-i)));
}
for(int i=start; i>=0; i--){
upd(pos[i], 0);
}
}
long long int findMaxAttraction(int nn, int start, int D, int attraction[]) {
d=D;
n=nn;
rep(i,0,n-1) A[i]=attraction[i];
vector<pair<int, int>> v;
rep(i,0,n-1) v.pb({A[i], i});
sort(v.begin(), v.end());
rep(i,0,n-1) pos[v[i].s]=i;
line(start);
go(start);
for(int i=0; n-1-i>i; i++) swap(A[i], A[n-1-i]), swap(pos[i], pos[n-1-i]);
go(n-1-start);
return ans;
}
