#include <bits/stdc++.h>
//#include "Lgrader.cpp"
#define endl '\n'
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
struct node
{
int cnt;
int64_t sum;
node *l, *r;
node() { l = r = nullptr; sum = cnt = 0; }
};
using pnode = node*;
pnode merge(pnode l, pnode r)
{
pnode ret = new node();
ret->l = l;
ret->r = r;
ret->cnt = l->cnt + r->cnt;
ret->sum = l->sum + r->sum;
return ret;
}
vector<int> cmpr;
int get(int x) { return lower_bound(cmpr.begin(), cmpr.end(), x) - cmpr.begin(); }
int SZ;
pnode build(int l, int r)
{
if(l == r)
return new node();
int mid = (l + r) >> 1;
return merge(build(l, mid), build(mid + 1, r));
}
pnode add(int x, int l, int r, pnode t)
{
if(x < l || x > r)
return t;
if(l == r)
{
pnode it = new node();
it->cnt = t->cnt + 1;
it->sum = t->sum + cmpr[SZ - x];
return it;
}
int mid = (l + r) >> 1;
return merge(add(x, l, mid, t->l), add(x, mid + 1, r, t->r));
}
int64_t get(int k, int l, int r, pnode A, pnode B)
{
if(l == r)
{
int c = min(k, A->cnt - B->cnt);
int64_t ret = c * 1ll * cmpr[SZ - l];
return ret;
}
int mid = (l + r) >> 1;
if(A->l->cnt - B->l->cnt < k) return A->l->sum - B->l->sum + get(k - (A->l->cnt - B->l->cnt), mid + 1, r, A->r, B->r);
else return get(k, l, mid, A->l, B->l);
}
int n, a[MAXN], start, d;
pnode t[MAXN], emp, last;
int64_t eval(int l, int r)
{
int cnt = (r - l) * 2 - max(abs(start - l), abs(start - r));
cnt = max(0, d - cnt);
if(l == 0) return get(cnt, 0, SZ, t[r], emp);
else return get(cnt, 0, SZ, t[r], t[l - 1]);
}
int opt[MAXN];
int64_t value[MAXN];
void rec(int l, int r, int opt_l, int opt_r)
{
if(l > r)
return;
int mid = (l + r) >> 1;
opt[mid] = l;
value[mid] = -(int64_t)1e18;
for(int i = opt_l; i <= opt_r; i++)
if(chkmax(value[mid], eval(mid, i)))
opt[mid] = i;
rec(l, mid - 1, opt_l, opt[mid]);
rec(mid + 1, r, opt[mid], opt_r);
}
long long findMaxAttraction(int n, int start, int d, int attraction[])
{
::n = n;
::start = start;
::d = d;
for(int i = 0; i < n; i++)
a[i] = attraction[i];
for(int i = 0; i < n; i++) cmpr.push_back(a[i]);
sort(cmpr.begin(), cmpr.end());
cmpr.erase(unique(cmpr.begin(), cmpr.end()), cmpr.end());
SZ = cmpr.size() - 1;
last = emp = build(0, SZ);
for(int i = 0; i < n; i++)
last = t[i] = add(SZ - get(a[i]), 0, SZ, last);
rec(0, start, start, n - 1);
int64_t answer = 0;
for(int i = 0; i < n; i++)
chkmax(answer, value[i]);
/*for(int i = 0; i <= start; i++)
for(int j = start; j < n; j++)
//cout << i << " " << j << " : " << eval(i, j) << endl;
chkmax(answer, eval(i, j));
*/
return answer;
}
