#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define pb push_back
#define ff first
#define ss second
pli operator + (pli x, pli y){
return {x.ff + y.ff, x.ss + y.ss};
}
pli operator - (pli x, pli y){
return {x.ff - y.ff, x.ss - y.ss};
}
struct PST{
struct node{
int l, r;
ll s; int c;
node(){
l = r = 0;
s = c = 0;
}
node(ll x, int y){
l = r = 0;
s = x;
c = y;
}
};
vector<node> t;
int merge(int ls, int rs){
node out;
out.l = ls; out.r = rs;
out.s = t[ls].s + t[rs].s;
out.c = t[ls].c + t[rs].c;
t.pb(out);
return ++cc;
}
int nw(){
t.pb(node());
return ++cc;
}
int nw(ll x, int y){
t.pb(node(x, y));
return ++cc;
}
vector<int> root;
int build(int tl, int tr){
if (tl == tr) return nw();
int tm = (tl + tr) / 2;
return merge(build(tl, tm), build(tm + 1, tr));
}
int n, cc, vv;
vector<int> a;
vector<int> :: iterator it;
void init(int ns, vector<int> as){
root.clear();
root.resize(ns + 1);
sort(as.begin() + 1, as.end());
a = {0};
int i = 1;
while (i < as.size()){
int j = i;
while (j < as.size() && as[i] == as[j]){
j++;
}
a.pb(as[i]);
i = j;
}
n = (int) a.size() - 1;
t.clear();
t.pb(node());
cc = vv = 0;
build(1, n);
}
int upd(int v, int tl, int tr, int& p, int& x){
if (tl == tr) return nw(t[v].s + x, t[v].c + 1);
int tm = (tl + tr) / 2;
if (p <= tm){
return merge(upd(t[v].l, tl, tm, p, x), t[v].r);
}
else {
return merge(t[v].l, upd(t[v].r, tm + 1, tr, p, x));
}
}
void upd(int x){
vv++;
it = lower_bound(a.begin() + 1, a.end(), x);
int i = (int) (it - a.begin());
root[vv] = upd(root[vv - 1], 1, n, i, x);
}
ll find(int v1, int v2, int tl, int tr, int k){
if (tl == tr) return 1LL * a[tl] * k;
int s = t[t[v2].l].c - t[t[v1].l].c, tm = (tl + tr) / 2;
ll sum = t[t[v2].l].s - t[t[v1].l].s;
if (k <= s){
return find(t[v1].l, t[v2].l, tl, tm, k);
}
return sum + find(t[v1].r, t[v2].r, tm + 1, tr, k - s);
}
ll get(int l, int r, int k){
k = min(k, r - l + 1);
return find(root[l - 1], root[r], 1, n, k);
}
};
PST T;
ll get(vector<int> a, int n, int x, int d){
T.init(n, a);
for (int i = 1; i <= n; i++){
T.upd(a[i]);
}
auto f = [&](int l, int r){
int f = d - (x - l) - (r - l);
return -T.get(l, r, f);
};
ll out = 0;
function<void(int, int, int, int)> solve = [&](int l, int r, int l1, int r1){
if (l > r) return;
int m = (l + r) / 2;
pli mx = {-1, 0};
for (int i = l1; i <= r1; i++){
mx = max(mx, {f(m, i), -i});
}
out = max(out, mx.ff);
mx.ss = -mx.ss;
solve(l, m - 1, l1, mx.ss);
solve(m + 1, r, mx.ss, r1);
};
solve(1, x, x, n);
return out;
}
ll findMaxAttraction(int n, int x, int d, int A[]){
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
a[i] = -A[i - 1];
}
x++;
ll out = get(a, n, x, d);
reverse(a.begin() + 1, a.end());
x = n + 1 - x;
out = max(out, get(a, n, x, d));
return out;
}
