#include"holiday.h"
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define ll long long
#define MAXN 200005
#define LOGN 20
const int modulo = 1e9+7;
const ll INF = 2e18 + 7;
void compute_dc_dp2(int l, int r, int L, int R, ll curr_sum, int flag, vector<int> &arr, vector<ll> &dp){
vector<array<int, 4>> ranges, tmp;
ranges.pb({l, r, L, R});
for (int i = 0; i < LOGN; i++){
auto it = 0;
multiset<int> curr[2];
curr[1].insert(arr[it]);
ll curr_sum = 0;
tmp.clear();
for (auto j : ranges){
int l = j[0], r = j[1], sl = j[2], sr = j[3];
int mid = (l + r) / 2;
pair<ll, ll> opt = {0, sl};
int start = it;
while(it <= sr){
if (it * flag > mid) break;
if (it != start) { //umm, not fully sure of this but whatever
curr[1].insert(arr[it]);
}
while(curr[0].size() < mid - flag * it && !curr[1].empty()){
int top = *curr[1].rbegin();
curr[1].erase(curr[1].find(top));
curr_sum += top;
curr[0].insert(top);
}
while(curr[0].size() > mid - flag * it){
int top = *curr[0].begin();
curr[0].erase(curr[0].begin());
curr_sum -= top;
curr[1].insert(top);
}
while(!curr[0].empty() && !curr[1].empty() && *curr[0].begin() < *curr[1].rbegin()){
int top = *curr[1].rbegin();
curr[1].erase(curr[1].find(top));
curr_sum += top;
curr[0].insert(top);
top = *curr[0].begin();
curr[0].erase(curr[0].begin());
curr_sum -= top;
curr[1].insert(top);
}
if (it >= sl) opt = max(opt, {curr_sum, it});
it++;
}
int pos = opt.nd;
dp[mid] = opt.st;
//cout<<mid<<" : "<<sp<<sl<<sp<<sr<<sp<<sp<<curr_sum<<sp<<curr[0].size()<<sp<<curr[1].size()<<sp<<opt.st<<sp<<opt.nd<<endl;
if (l < mid) tmp.pb({l, mid - 1, sl, pos});
if (r > mid) tmp.pb({mid + 1, r, pos, sr});
it--;
}
swap(tmp, ranges);
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<ll> lft[2], rgt[2];
for (int i = 0; i < 2; i++){
lft[i].resize(d + 1, 0);
rgt[i].resize(d + 1, 0);
}
vector<int> L, R;
L.pb(0), R.pb(0);
for (int i = start - 1; i >= 0; i--){
L.pb(attraction[i]);
}
compute_dc_dp2(0, d, 0, L.size() - 1, 0, 1, L, lft[0]);
compute_dc_dp2(0, d, 0, L.size() - 1, 0, 2, L, lft[1]);
for (int i = start + 1; i < n; i++)
R.pb(attraction[i]);
compute_dc_dp2(0, d, 0, R.size() - 1, 0, 1, R, rgt[0]);
compute_dc_dp2(0, d, 0, R.size() - 1, 0, 2, R, rgt[1]);
/*
for (int i = 0; i < d; i++)
cout<<i<<sp<<1<<" : "<<lft[0][i]<<endl;*/
ll ans = 0;
for (int i = 0; i <= d; i++){
ll t1 = lft[0][i] + rgt[1][d - i];
ll t2 = lft[1][i] + rgt[0][d - i];
ll t3 = 0, t4 = 0;
if (i < d) t3 = lft[0][i] + rgt[1][d - i - 1] + attraction[start];
if (i < d) t4 = lft[1][i] + rgt[0][d - i - 1] + attraction[start];
ans = max(ans, max(t1, t2));
ans = max(ans, max(t3, t4));
}
return ans;
}
/*
int main() {
fileio();
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
*/
