#include<bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7;
int start, d, a[N];
ll ans = 0;
ll get(int l, int r) {
if (start < l || start > r) {
cout << "LMAO" << endl;
exit(1);
}
int go = (start - l) + (r - start) + min(start - l, r - start);
if (go > d)
return 0;
int k = d - go;
vector <int> v;
for (int i = l; i <= r; ++i)
v.app(a[i]);
sort(all(v)); reverse(all(v));
ll ans = 0;
for (int i = 0; i < k && i < v.size(); ++i)
ans += v[i];
return ans;
}
int get_opt(int r, int opt_l, int opt_r) {
ll nn = 0, opt = opt_l;
for (int l = opt_l; l <= opt_r; ++l) {
ll t = get(l, r);
if (t > nn) {
nn = t;
opt = l;
}
}
ans = max(ans, nn);
return opt;
}
void solve(int l, int r, int opt_l, int opt_r) {
if (r < l)
return;
int m = (l + r) >> 1;
int opt_m = get_opt(m, opt_l, opt_r);
solve(l, m - 1, opt_l, opt_m);
solve(m + 1, r, opt_m, opt_r);
}
long long int findMaxAttraction(int n, int start_, int d_, int a_[]) {
start = start_;
d = d_;
for (int i = 0; i < n; ++i)
a[i] = a_[i];
solve(start, n - 1, 0, start);
return ans;
}
