#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
const int INF = 1e9 + 7;
const int maxn = 1e5 + 10;
int n, s, d, a[maxn];
int calc_dist(int l, int r){
if (l >= s) return r - s;
if (r <= s) return s - l;
return r - l + min(r - s, s - l);
}
ll solve(int l){
// cout << "kore wa beginning" << endl;
// cout << n << ' ' << ' ' << s << ' ' << d << endl;
set<pii> include, removed; ll best = 0, include_sum = 0;
for (int i = l; i <= s; i++){
removed.insert({a[i], i});
}
for (int r = s + 1; r < n; r++){
if (calc_dist(l, r) > d) break;
// cout << l << ' ' << r << endl;
removed.insert({a[r], r});
// while (calc_dist(l, r) > d){
// if (include.count({a[l], l})){
// include.erase({a[l], l});
// include_sum -= a[l];
// }
// else removed.erase({a[l], l});
// l++;
// }
// rebalance
while (include.size() > 0 && removed.size() > 0 &&
include.begin()->F < removed.rbegin()->F){
pii x = *include.begin(), y = *removed.rbegin();
include_sum -= x.F; include.erase(x);
removed.erase(y);
include_sum += y.F; include.insert(y);
removed.insert(x);
}
// adding elements if we can
int can_include = d - calc_dist(l, r);
while (include.size() < can_include && removed.size() > 0){
pii x = *removed.rbegin(); removed.erase(x);
include_sum += x.F; include.insert(x);
}
// removing elements if we must
while (include.size() > can_include){
pii x = *include.begin(); include.erase(x);
include_sum -= x.F; removed.insert(x);
}
// while (l < s){
// int can_include = d - calc_dist(l, r);
// int can_include_prime = d - calc_dist(l + 1, r);
// ll delta = 0;
// if (include.count({a[l], l})){
// delta -= a[l];
// can_include_prime++;
// }
// else{
// removed.erase({a[l], l});
// }
// auto it = removed.rbegin();
// vector<pii> to_remove;
// FOR(_, min((int)removed.size(), can_include_prime - can_include)){
// to_remove.push_back(*it);
// delta += it->F; it++;
// }
// if (delta < 0 && include.count({a[l], l})) break;
// if (include.count({a[l], l})){
// include.erase({a[l], l});
// }
// for (auto x : to_remove){
// removed.erase(x);
// include.insert(x);
// }
// include_sum += delta; l++;
// }
// cout << l << ' ' << r << endl;
// if (l == 27 && r == 588) cout << include_sum << endl;
// assert(!(l == 27 && r == 588));
best = max(best, include_sum);
}
return best;
}
ll heh(int l, int r){
int can_include = d - calc_dist(l, r);
priority_queue<int> pq;
for (int i = l; i <= r; i++) pq.push(a[i]);
ll sum = 0;
while (!pq.empty() && can_include > 0){
sum += pq.top(); pq.pop();
can_include--;
}
return sum;
}
ll findMaxAttraction(int N, int start, int D, int attraction[]){
n = N, s = start, d = D;
for (int i = 0; i < n; i++) a[i] = attraction[i];
// ll best = 0; int best_l, best_r;
// for (int l = 0; l < n; l++){
// for (int r = l; r < n; r++){
// ll ans = heh(l, r);
// if (ans > best) best = ans, best_l = l, best_r = r;
// }
// }
// cout << best_l << ' ' << best_r << endl;
// return best;
ll re = 0;
for (int l = 0; l <= s; l++){
re = max(re, solve(l));
}
return re;
// ll re = solve();
// reverse(a, a + n); s = n - 1 - start;
// re = max(re, solve());
// return re;
}
