#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, sum = 0;
long long dp[300010], opt[300010], dps[300010], opts[300010], idx[300010];
vector<pair<int, int> > v;
priority_queue<int, vector<int>, greater<int> > pq;
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){
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;
int m = (l + r) >> 1;
dp[m] = 0, opt[m] = -1;
while(now < optL) update(idx[++now], 1);
while(now > optL) update(idx[now--], 0);
for(int i = optL; i <= m + pvt && i <= optR; i++){
if(now < i) update(idx[++now], 1);
long long x = query(m - (i - pvt));
if(dp[m] < x){
dp[m] = x;
opt[m] = i;
}
}
solve(l, m - 1, optL, opt[m], pvt);
solve(m + 1, r, opt[m], optR, pvt);
}
void solveS(int l, int r, int optL, int optR, int pvt){
if(l > r || optR < 0) return;
int m = (l + r) >> 1;
dps[m] = 0, opts[m] = -1;
while(optR < now) update(idx[--now], 1);
while(now < optR) update(idx[now++], 0);
for(int i = optR; pvt - i <= m && i >= optL; i--){
if(now > i) update(idx[--now], 1);
long long x = query(m - (pvt - i));
if(dps[m] < x){
dps[m] = x;
opts[m] = i;
}
}
solveS(l, m - 1, opts[m], optR, pvt);
solveS(m + 1, r, optL, opts[m], 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;
solveS(0, d, 0, start - 1, start - 1);
for(int i = 0; i <= d; i++){
// cerr << i << " -> " << dps[i] << " " << opts[i] << endl;
// cerr << d - i - (opt[i] - start) - 1 << endl;
ans = max(ans, max(dp[i], dps[i]));
//Go right, then left
if(opt[i] != -1 && d - i - (opt[i] - start) - 1 > 0) ans = max(ans, dp[i] + dps[d - i - (opt[i] - start) - 1]);
//Go left, then right
if(opts[i] != -1 && d - i - (start - 1 - opts[i]) - 1 > 0) ans = max(ans, dps[i] + dp[d - i - (start - 1 - opts[i]) - 1]);
}
return ans;
}
