#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
struct Node{
long long val = 0;
int active = 0;
};
int n;
Node st[400010];
long long int ans;
int idx[300010];
vector<pair<int, int> > v;
long long f[300010], g[300010];
int optF[300010], optG[300010];
void update(int l, int r, int pt, bool val, int i){
if(pt < l || r < pt) return;
if(l == r && l == pt){
st[i].active = val;
if(st[i].active) st[i].val = v[l].first;
else st[i].val = 0;
return;
}
int m = (l + r) >> 1;
update(l, m, pt, val, i << 1);
update(m + 1, r, pt, val, 1 + (i << 1));
st[i].val = st[i << 1].val + st[1 + (i << 1)].val;
st[i].active = st[i << 1].active + st[1 + (i << 1)].active;
}
long long query(int l, int r, int val, int i){
if(val == 0) return 0;
if(st[i].active <= val) return st[i].val;
int m = (l + r) >> 1;
return query(l, m, min(val, st[i << 1].active), i << 1) + query(m + 1, r, max(0, val - st[i << 1].active), 1 + (i << 1));
}
void update(int pt, bool val){
update(0, n - 1, pt, val, 1);
}
long long query(int val){
if(val <= 0) return 0;
return query(0, n - 1, val, 1);
}
int now;
void solve(int l, int r, int optL, int optR, int pvt){
if(l > r) return;
long long val = -1;
int opt = -1;
int m = (l + r) >> 1;
while(now < optL) update(idx[++now], 1);
while(now > optL) update(idx[now--], 0);
for(int i = optL; i <= optR; i++){
if(now < i) update(idx[++now], 1);
long long x = query(m - (i - pvt));
if(x > val){
val = x;
opt = i;
}
}
f[m] = val;
optF[m] = opt;
solve(l, m - 1, optL, opt, pvt);
solve(m + 1, r, opt, optR, pvt);
}
void solveS(int l, int r, int optL, int optR, int pvt){
if(l > r) return;
long long val = -1;
int opt = -1;
int m = (l + r) >> 1;
while(now > optR) update(idx[--now], 1);
while(now < optR) update(idx[now++], 0);
for(int i = optR; i >= optL; i--){
if(now > i) update(idx[--now], 1);
long long x = query(m - (pvt - i));
if(x > val){
val = x;
opt = i;
}
}
g[m] = val;
optG[m] = opt;
solveS(l, m - 1, opt, optR, pvt);
solveS(m + 1, r, optL, opt, pvt);
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
n = N;
for(int i = 0; i < n; i++) v.emplace_back(attraction[i], i);
sort(v.rbegin(), v.rend());
for(int i = 0; i < n; i++){
idx[v[i].second] = i;
}
now = start - 1;
solve(0, d, start, n - 1, start);
while(now >= start) update(idx[now--], 0);
now = start;
if(start > 0) solveS(0, d, 0, start - 1, start - 1);
for(int i = 1; i <= d; i++){
// cout << i << " -> " << g[i] << " " << optG[i] << endl;
ans = max(ans, max(f[i], g[i - 1]));
if(d - i - (optF[i] - start) - 1 > 0) ans = max(ans, f[i] + g[d - i - (optF[i] - start) - 1]);
if(d - (i + 1) - (start - 1 - optG[i]) - 1 > 0) ans = max(ans, g[i] + f[d - i - (start - optG[i]) - 1]);
}
return ans;
}
