#include <bits/stdc++.h>
#include"holiday.h"
#pragma GCC optimize("Ofast")
#define ll long long
using namespace std;
const int L = 131072;
vector<int> t[2*L];
vector<ll> p[2*L];
int num(int l, int r, int x){
int s = 0;
l += L, r += L;
while(l <= r){
if(l&1) s += upper_bound(t[l].begin(), t[l].end(), x, greater<int>())-t[l].begin(), l++;
if(!(r&1)) s += upper_bound(t[r].begin(), t[r].end(), x, greater<int>())-t[r].begin(), r--;
l >>= 1, r >>= 1;
}
return s;
}
ll qry(int l, int r, int x, ll &mi){
ll s = 0;
l += L, r += L;
while(l <= r){
if(l&1){
int idx = upper_bound(t[l].begin(), t[l].end(), x, greater<int>())-t[l].begin()-1;
if(idx >= 0) s += p[l][idx];
if(idx+1 < (int)p[l].size()) mi = max(mi, (ll)t[l][idx+1]);
l++;
}
if(!(r&1)){
int idx = upper_bound(t[r].begin(), t[r].end(), x, greater<int>())-t[r].begin()-1;
if(idx >= 0) s += p[r][idx];
if(idx+1 < (int)p[r].size()) mi = max(mi, (ll)t[r][idx+1]);
r--;
}
l >>= 1, r >>= 1;
}
return s;
}
ll sum(int l, int r, int k){
k = min(k, r-l+1);
int a = 0, b = 1e9, m;
while(a < b){
if(a == b-1){
if(num(l, r, a) <= k) b--;
else a++;
}
else{
m = (a+b)/2;
if(num(l, r, m) <= k) b = m;
else a = m+1;
}
}
ll mi = 0, ret = qry(l, r, a, mi);
ret += mi*(k-num(l, r, a));
return ret;
}
void div1(int s, int d, int l, int r, int optl, int optr, ll& sol){
if(l > r) return;
ll best = -1;
int opt = -1, m = (l+r)/2;
for(int i = min(optr, max(optl, (d+s+2*m-1)/3)); i <= optr; i++){
ll temp = sum(m, i, max(0, d-2*(i-s)-(s-m)));
if(temp > best) best = temp, opt = i;
}
sol = max(sol, best);
div1(s, d, l, m-1, optl, opt, sol), div1(s, d, m+1, r, opt, optr, sol);
}
void div2(int s, int d, int l, int r, int optl, int optr, ll& sol){
if(l > r) return;
ll best = -1;
int opt = -1, m = (l+r)/2;
for(int i = optl; i <= max(optl, min(optr, (s-d+2*m+1)/3)); i++){
ll temp = sum(i, m, max(0, d-2*(s-i)-(m-s)));
if(temp > best) best = temp, opt = i;
}
sol = max(sol, best);
div2(s, d, l, m-1, optl, opt, sol), div2(s, d, m+1, r, opt, optr, sol);
}
ll findMaxAttraction(int n, int start, int d, int attraction[]){
for(int i = 0; i < n; i++) t[i+L] = {attraction[i]}, p[i+L] = {attraction[i]};
for(int i = L-1; i; i--){
merge(begin(t[i<<1]), end(t[i<<1]), begin(t[i<<1|1]), end(t[i<<1|1]), back_inserter(t[i]),
greater<int>());
for(int j = 0; j < (int)t[i].size(); j++){
p[i].push_back(t[i][j]);
if(j) p[i].back() += p[i][p[i].size()-2];
}
}
ll sol = 0;
div1(start, d, 0, start, start, n-1, sol), div2(start, d, start, n-1, 0, start, sol);
return sol;
}
