#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool cmp(pair<int,int> a, pair<int,int> b) {
if (a.first != b.first) return a.first > b.first;
return a.second < b.second;
}
const int maxn = 1e5 + 5;
int n, s, d;
int a[maxn], fen[maxn][2];
void update(int id, int val, int j) {
for (; id<=n; id += (id & -id)) fen[id][j] += val;
}
int qry(int id, int j) {
int val = 0;
for (;id>=1;id -= (id & -id)) val += fen[id][j];
return val;
}
int get(int l, int r) {
int k = min(d - (r-l) - min(r-s, s-l), r-l+1);
vector<int> v;
for (int i=l;i<=r;i++) v.push_back(a[i]);
sort(v.rbegin(), v.rend());
int val = 0;
for (int i=0;i<k;i++) val += v[i];
// cout << l << " " << r << " " << val << endl;
return val;
}
int solve() {
vector<pair<int,int>> v;
for (int i=s;i<=n;i++) v.push_back({a[i], i});
for (int i=0;i<=n;i++) fen[i][0] = 0, fen[i][1] = 0;
sort(v.rbegin(), v.rend());
int mx = 0, r = n;
for (auto [val, id]:v) {
update(id, val, 0);
update(id, 1, 1);
while (r-s + qry(r, 1) > d) r--;
mx = max(qry(r, 0), mx);
}
// cout << mx << endl;
for (int i=0;i<=n;i++) fen[i][0] = 0, fen[i][1] = 0;
sort(v.begin(), v.end(), cmp);
vector<int> vec;
r = n;
for (auto [val, id]:v) {
update(id, val, 0);
update(id, 1, 1);
while (r-s + qry(r, 1) > d) r--;
if (qry(r, 0) == mx) {
// cout << qry(r, 1) << endl;
for (int i=s;i<=r;i++) if (qry(i, 1) - qry(i-1, 1) == 1) {
// cout << i << " ";
vec.push_back(i);
}
// cout << endl;
}
}
int ans = 0;
for (int l = s, R = vec.size()-1; l>=1; l--) {
while (R >= 0 && vec[R]-l + s-l + R+1 > d) R--;
if (R<0 || vec[R] - s < s - l) break;
ans = max(get(l, vec[R]), ans);
}
return ans;
}
int findMaxAttraction(int32_t N, int32_t S, int32_t D, int32_t A[]) {
n = N, s = S+1, d = D;
for (int i=1;i<=n;i++) a[i] = A[i-1];
int ans = solve();
reverse(a+1, a+n+1);
s = n+1-s;
ans = max(solve(), ans);
return ans;
}
