// In the name of Allah
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = (1 << 17) + 7;
const int oo = 1e9 + 7;
int n, v, d;
ll a[maxn]; int ind[maxn];
pll t[2 * maxn], A[maxn];
ll res;
pll add_pair(pll a, pll b) {
return Mp(a.F + b.F, a.S + b.S);
}
void add_val(int v, int tl, int tr, int i, pll x) {
if (i >= tr || i < tl) return ;
if (tr - tl == 1) {
t[v] = add_pair(t[v], x);
return ;
}
int mid = (tl + tr) / 2;
add_val(2 * v + 1, tl, mid, i, x); add_val(2 * v + 2, mid, tr, i, x);
t[v] = add_pair(t[2 * v + 1], t[2 * v + 2]);
}
ll get_val(int v, int tl, int tr, ll x) {
x = min(x, t[v].S);
if (x == 0) return 0;
if (tr - tl == 1) return t[v].F;
int mid = (tl + tr) / 2;
if (t[2 * v + 2].S >= x) return get_val(2 * v + 2, mid, tr, x);
else return t[2 * v + 2].F + get_val(2 * v + 1, tl, mid, x - t[2 * v + 2].S);
}
void get_opt(int l, int r, int lx, int rx) {
if (r - l < 1) return ;
int mid = (l + r) / 2;
int j = mid, k = -1; ll valx = -oo;
for (int i = mid; i < min(r, v); i++) add_val(0, 0, n, ind[i], Mp(a[i], 1));
for (int i = lx; i < rx; i++) {
add_val(0, 0, n, ind[i], Mp(a[i], 1));
int R = d - ((i - j) + min(i - v, v - j));
if (R < 0) break;
ll x = get_val(0, 0, n, R);
if (x > valx) {
k = i; valx = x;
}
}
res = max(res, valx);
for (int i = lx; i < rx; i++) {
add_val(0, 0, n, ind[i], Mp(-a[i], -1));
int R = d - ((i - j) + min(i - v, v - j));
if (R < 0) break;
}
get_opt(l, mid, lx, k + 1);
for (int i = mid; i < min(r, v); i++) add_val(0, 0, n, ind[i], Mp(-a[i], -1));
for (int i = lx; i < k; i++) add_val(0, 0, n, ind[i], Mp(a[i], 1));
get_opt(mid + 1, r, k, rx);
for (int i = lx; i < k; i++) add_val(0, 0, n, ind[i], Mp(-a[i], -1));
}
ll findMaxAttraction(int Nx, int Sx, int Dx, int Ax[]) {
n = Nx; v = Sx; d = Dx;
for (int i = 0; i < n; i++) {
a[i] = Ax[i];
A[i] = Mp(a[i], i);
}
sort(A, A + n);
for (int i = 0; i < n; i++) {
ind[i] = lower_bound(A, A + n, (pll) Mp(a[i], i)) - A;
}
res = 0;
int l = max(0, v - d), r = v + 1;
int lx = v, rx = min(n, v + d + 1);
get_opt(l, r, lx, rx);
return res;
}
