#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
#define endl "\n"
#define long long long int
#define sz(x) int((x).size())
struct DS {
vector<vector<long>> ans;
DS(const vector<int>& arr) {
for (int i = 0; i < sz(arr); i++) {
vector<long> tmp(arr.begin(), arr.begin() + i + 1);
sort(begin(tmp), end(tmp), greater<>());
ans.emplace_back(i + 2);
partial_sum(begin(tmp), end(tmp), ans[i].begin() + 1);
}
}
long query(int i, int k) {
if (k < 0) {
return 0;
}
return ans[i][min(i + 1, k)];
}
};
int m;
struct Pref {
int mul;
vector<int> arr;
DS ds;
vector<long> ans;
Pref(int mul, const vector<int>& arr)
: mul(mul), arr(arr), ds(arr), ans(m + 1) {}
void dp(int l, int r, int ql, int qr) {
if (l > r) {
return;
}
int mid = (l + r) / 2;
pair<long, int> opt {-1, -1};
for (int i = ql; i <= qr; i++) {
opt = max(opt,
pair<long, int> {ds.query(i, mid - (i + 1) * mul), -i});
}
auto& [cans, qmid] = opt;
qmid = -qmid;
ans[mid] = cans;
dp(l, mid - 1, ql, qmid);
dp(mid + 1, r, qmid, qr);
}
vector<long> solve() {
if (sz(arr)) {
dp(0, m, 0, sz(arr) - 1);
}
return ans;
}
};
template <typename T>
T reversed(T t) {
reverse(begin(t), end(t));
return t;
}
long solve(int start, const vector<int>& arr) {
auto suff =
Pref(2, vector<int>(arr.begin() + start + 1, arr.end())).solve();
auto pref = Pref(1, reversed(vector<int>(arr.begin(), arr.begin() + start)))
.solve();
long ans = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j <= m; j++) {
int k = m - j - i;
if (k >= 0) {
ans = max(ans, i * arr[start] + suff[j] + pref[k]);
}
}
}
return ans;
}
long findMaxAttraction(int n, int start, int _m, int inarr[]) {
m = _m;
vector<int> arr(inarr, inarr + n);
return max(solve(start, arr), solve(n - start - 1, reversed(arr)));
}
