#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 4e6 + 100;
pair <ll, ll> seg[N];
int n;
void upd(int id, int l, int r, int x, int v, int add) {
if (l > x || r < x)
return;
if (l == r) {
seg[id].f += v;
seg[id].s += add;
return;
}
int m = (l + r) / 2;
upd(id * 2, l, m, x, v, add);
upd(id * 2 + 1, m + 1, r, x, v, add);
seg[id].f = seg[id * 2].f + seg[id * 2 + 1].f;
seg[id].s = seg[id * 2].s + seg[id * 2 + 1].s;
}
ll get(int id, int l, int r, ll cnt) {
if (seg[id].f <= cnt)
return seg[id].s;
if (l == r) {
return min((seg[id].s / seg[id].f) * cnt, seg[id].s);
}
int m = (l + r) / 2;
if (seg[id * 2 + 1].f >= cnt)
return get(id * 2 + 1, m + 1, r, cnt);
return get(id * 2, l, m, cnt - seg[id * 2 + 1].f) + seg[id * 2 + 1].s;
}
int L, R;
vector <int> v, rnk;
void move(int l, int r) {
while (L < l) {
upd(1, 0, n - 1, rnk[L], -1, -v[L]);
L++;
}
while (L > l) {
L--;
upd(1, 0, n - 1, rnk[L], 1, v[L]);
}
while (R < r) {
R++;
upd(1, 0, n - 1, rnk[R], 1, v[R]);
}
while (R > r) {
upd(1, 0, n - 1, rnk[R], -1, -v[R]);
R--;
}
}
ll cal(int v) {
if (v < 0)
return 0;
return get(1, 1, n, v);
}
void maximize(pair <ll, ll> &a, pair <ll, ll> b) {
if (a.f < b.f) {
a = b;
} else {
if (a.f == b.f) {
a.s = min(a.s, b.s);
}
}
}
void dnc(int st, int l1, int r1, int l, int r, vector <pair <ll, ll>> &f) {
if (l1 > r1 || st < 0)
return;
int m1 = (l1 + r1) / 2;
for (int i = l; i <= r; i++) {
move(min(st, i), max(st, i));
ll v = cal(m1 - abs(i - st));
maximize(f[m1], {v, abs(i - st)});
}
int opt = f[m1].s;
if (r >= st && l >= st) {
dnc(st, l1, m1 - 1, l, opt + st, f);
dnc(st, m1 + 1, r1, opt + st, r, f);
} else {
dnc(st, m1 + 1, r1, l, st - opt, f);
dnc(st, l1, m1 - 1, st - opt, r, f);
}
}
ll findMaxAttraction(int _n, int st, int d, int att[]) {
n = _n;
map <int, int> mp;
int timer = 0;
for (int i = 0; i < n; i++) {
v.pb(att[i]);
mp[att[i]];
}
for (auto &x : mp) {
x.s = timer;
timer++;
}
for (auto x : v)
rnk.pb(mp[x]);
L = R = 0;
upd(1, 0, n - 1, rnk[L], 1, v[L]);
vector <pair <ll, ll>> d1(d + 1, {0, 0}), d2(d + 1, {0, 0});
dnc(st, 0, d, st, n - 1, d1);
dnc(st - 1, 0, d, 0, st - 1, d2);
ll ans = d1[d].f;
for (int i = 0; i < d; i++) {
auto t = d1[i];
int v = t.s + 1;
if (v + i <= d) {
ans = max(ans, t.f + d2[d - v - i].f);
}
t = d2[i];
v = t.s + 2;
if (v + i <= d) {
ans = max(ans, t.f + d1[d - v - i].f);
}
}
return ans;
}
