#include "bits/stdc++.h"
#include"holiday.h"
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll c[N], sum[4 * N], cnt[4 * N], lazy[4 * N], pos[N], bruh, ccc[N];
pair<ll, ll> rr[5 * N];
ll query(int i, int l, int r, int k) {
if(l > r || k <= 0) return 0;
if(cnt[i] <= k) return sum[i];
int mid = l + r >> 1;
if(cnt[2 * i] > k) return query(2 * i, l, mid, k);
return sum[2 * i] + query(2 * i + 1, mid + 1, r, k - cnt[2 * i]);
}
void modif(int i, int l, int r, int pos, bool b) {
if(l > pos || r < pos) return;
if(l == pos && r == pos) {
sum[i] = (b ? c[l] : 0);
cnt[i] = b;
return;
}
int mid = l + r >> 1;
modif(2 * i, l, mid, pos, b);
modif(2 * i + 1, mid + 1, r, pos, b);
sum[i] = sum[2 * i] + sum[2 * i + 1];
cnt[i] = cnt[2 * i] + cnt[2 * i + 1];
}
int L, R;
void move_pointers(int l, int r) {
while(L > l) {
--L;
++ccc[L];
if(ccc[L] == 1) modif(1, 0, N - 1, pos[L], 1);
}
while(L < l) {
if(ccc[L] == 1) modif(1, 0, N - 1, pos[L], 0);
--ccc[L];
++L;
}
while(R < r) {
++R;
++ccc[R];
if(ccc[R] == 1) modif(1, 0, N - 1, pos[R], 1);
}
while(R > r) {
if(ccc[R] == 1) modif(1, 0, N - 1, pos[R], 0);
--ccc[R];
--R;
}
}
void rec(int dl, int dr, int l, int r, int start) {
if(l > r || dl > dr) return;
ll ans = 0, idx = l;
int d = ((dl + dr) >> 1) - abs(l - start);
for(int i = l; i <= r && d >= 0; ++i) {
move_pointers(0, i);
if(ans < query(1, 0, N - 1, d)) {
ans = query(1, 0, N - 1, d);
idx = i;
}
--d;
}
d = (dl + dr) >> 1;
rr[d] = {ans, idx};
if(dl == dr) return;
rec(dl, d - 1, l, idx, start);
rec(d + 1, dr, idx, r, start);
}
long long int findMaxAttraction(int n, int start, int d, int a[]) {
bruh = n;
vector<pair<int, int>> x;
for(int i = 0; i < n; ++i) x.push_back({a[i], i});
sort(x.rbegin(), x.rend());
for(int i = 0; i < n; ++i) {
c[i] = x[i].first;
pos[x[i].second] = i;
}
L = 0, R = n - 1;
for(int i = 0; i < n; ++i) {
ccc[i] = 1;
modif(1, 0, N - 1, pos[i], 1);
}
rec(1, 2 * n + n / 2 + 10, 0, n - 1, 0);
return rr[d].first;
}
