// M
#include<bits/stdc++.h>
#include"holiday.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 100005;
int n, st, d, A[N], Id[N], C[N * 4];
ll SM[N * 4];
vector < int > U;
ll MX;
void AddSeg(int i, int val, int id = 1, int l = 0, int r = (int)U.size())
{
C[id] += val;
SM[id] += (ll)val * U[i];
if (r - l < 2)
return ;
if (i < md)
AddSeg(i, val, lc, l, md);
else
AddSeg(i, val, rc, md, r);
}
ll GetSeg(int &k, int id = 1, int l = 0, int r = (int)U.size())
{
if (k <= 0)
return 0LL;
if (C[id] <= k)
return k -= C[id], SM[id];
if (r - l < 2)
{
ll rt = (ll)U[l] * k;
k = 0;
return rt;
}
ll rt = GetSeg(k, rc, md, r);
rt += GetSeg(k, lc, l, md);
return rt;
}
inline void Add(int i, int val)
{
AddSeg(Id[i], val);
}
ll Get(int k)
{
int kk = k;
return GetSeg(kk);
}
void Solve(int l, int r, int le, int ri)
{
if (r < l)
return ;
int opt = -1;
// [le, l) is added.
for (int i = l; i <= md; i ++)
Add(i, 1);
ll Mx = 0;
for (int i = le; i <= ri; i ++)
{
ll val = Get(d - min(md - st + md - i, md - i + st - i));
if (Mx < val)
Mx = val, opt = i;
Add(i, -1);
}
MX = max(MX, Mx);
// (ri, md]
for (int i = opt; i <= ri; i ++)
Add(i, 1);
// [opt, md]
Solve(md + 1, r, opt, ri);
for (int i = le; i < opt; i ++)
Add(i, 1);
// [le, md]
for (int i = l; i <= md; i ++)
Add(i, -1);
// [le, l)
Solve(l, md - 1, le, opt);
}
ll findMaxAttraction(int _n, int _start, int _d, int attraction[])
{
n = _n; st = _start; d = _d;
for (int i = 0; i < n; i ++)
A[i] = attraction[i], U.push_back(A[i]);
sort(U.begin(), U.end());
U.resize(unique(U.begin(), U.end()) - U.begin());
for (int i = 0; i < n; i ++)
Id[i] = lower_bound(U.begin(), U.end(), A[i]) - U.begin();
MX = 0;
for (int w = 0; w <= 1; w ++)
{
memset(C, 0, sizeof(C));
memset(SM, 0, sizeof(SM));
for (int i = st; i < n; i ++)
Add(i, 1), MX = max(MX, Get(d - (i - st)));
memset(C, 0, sizeof(C));
memset(SM, 0, sizeof(SM));
// Adding [le, l) :
for (int i = 0; i < st; i ++)
Add(i, 1);
Solve(st, n - 1, 0, st - 1);
for (int i = 0; i < st; i ++)
Add(i, -1);
reverse(A, A + n);
reverse(Id, Id + n);
st = n - 1 - st;
}
return MX;
}
