#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
const long long INF = 1e18;
long long A[maxn];
long long dpfx[maxn], dsfx[maxn];
int s, N, D;
int pos[maxn];
long long FW[2][maxn];
void add(int idx, long long val){
for(idx; idx <= N; idx += idx&(-idx)){
FW[0][idx] += val;
FW[1][idx]++;
}
}
long long gt(int k){
if(k < 0)return -INF;
int pos = 0;
long long sum = 0;
for(int i = 17; i >= 0; i--){
if(pos + (1<<i) > N)continue;
if(k - FW[1][pos^(1<<i)] >= 0){
pos^=(1<<i);
k -= FW[1][pos];
sum += FW[0][pos];
}
}
return sum;
}
void solve_pfx(){
queue<pair<pair<int, int>, pair<int, int>>> q;
int prv = 0, ptr = 0;
q.push({{0, D}, {s, 1}});
while(!q.empty()){
auto ele = q.front();
q.pop();
int l = ele.first.first, r = ele.first.second;
if(l > r)continue;
if(ele.second.second != prv){
prv = ele.second.second;
memset(FW, 0, sizeof(FW));
ptr = 0;
add(pos[s], A[s]);
}
int qr = ele.second.first;
int mid = (l+r)>>1, best = ptr;
dpfx[mid] = gt(mid - 2*ptr);
while(ptr < qr){
ptr++;
add(pos[s - ptr], A[s - ptr]);
long long tmp = gt(mid - 2*ptr);
if(tmp > dpfx[mid]){
dpfx[mid] = tmp;
best = ptr;
}
}
q.push({{l, mid-1}, {best, prv + 1}});
q.push({{mid+1, r}, {qr, prv + 1}});
}
}
void solve_sfx(){
queue<pair<pair<int, int>, pair<int, int>>> q;
int prv = 0, ptr = 0;
q.push({{0, D}, {N - s - 1, 1}});
while(!q.empty()){
auto ele = q.front();
q.pop();
int l = ele.first.first, r = ele.first.second;
if(l > r)continue;
if(ele.second.second != prv){
prv = ele.second.second;
memset(FW, 0, sizeof(FW));
ptr = 0;
}
int qr = ele.second.first;
int mid = (l+r)>>1, best = ptr;
dsfx[mid] = gt(mid - ptr);
while(ptr < qr){
ptr++;
add(pos[s + ptr], A[s + ptr]);
long long tmp = gt(mid - ptr);
if(tmp > dsfx[mid]){
dsfx[mid] = tmp;
best = ptr;
}
}
q.push({{l, mid-1}, {best, prv + 1}});
q.push({{mid+1, r}, {qr, prv + 1}});
}
}
long long solve(){
solve_pfx();
solve_sfx();
long long ans = -INF;
for(int i = 0; i <= D; i++){
ans = max(ans, dpfx[i] + dsfx[D - i]);
}
return ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
s = start;
N = n;
D = d;
vector<pair<int, int>> vec;
for(int i = 0; i < n; i++){
A[i] = attraction[i];
vec.push_back({A[i], i});
}
sort(vec.rbegin(), vec.rend());
for(int i = 0; i < n; i++)pos[vec[i].second] = i+1;
long long ans = solve();
reverse(pos, pos + n);
reverse(A, A+n);
s = n - s - 1;
ans = max(ans, solve());
return ans;
}
