#include <iostream>
#include <map>
using namespace std;
#define ll long long
const ll N = (1<<17) + 1;
ll cr, cnt[N<<1], Sum[N<<1], SumL[N<<2], SumR[N<<2], rgt[N<<2], lft[N<<2], rev[N], a[N];
map<ll, ll> mp, mp2;
void insert(ll i, ll t, ll cur = 1, ll st = 1, ll en = N){
if (i >= en or i < st)
return;
cnt[cur] += t;
Sum[cur] += t * rev[i];
if (en - st == 1)
return;
ll lc = cur<<1, rc = lc + 1, mid = (st + en)>>1;
insert(i, t, lc, st, mid);
insert(i, t, rc, mid, en);
}
ll get(ll k, ll cur = 1, ll st = 1, ll en = N){
if (en - st == 1)
return min(k, cnt[cur]) * rev[st];
ll lc = cur<<1, rc = lc + 1, mid = (st + en)>>1;
if (cnt[rc] <= k)
return Sum[rc] + get(k - cnt[rc], lc, st, mid);
return get(k, rc, mid, en);
}
void solve1(ll l, ll r, ll st, ll en, ll S){
if (l > r)
return;
ll mid = (l + r) / 2;
rgt[mid] = st;
for (ll i=st;i<=en;i++){
// turn it on
insert(a[i], 1);
ll nw = get(max(mid - (i - S), 0LL));
if (SumR[mid] < nw)
SumR[mid] = nw, rgt[mid] = i;
}
for (ll i=rgt[mid];i<=en;i++)
insert(a[i], -1);
// turn some off
solve1(mid + 1, r, rgt[mid], en, S);
for (ll i=st;i<rgt[mid];i++)
insert(a[i], -1);
// turn remaining off
solve1(l, mid - 1, st, rgt[mid], S);
}
void solve2(ll l, ll r, ll st, ll en, ll S){
if (l > r)
return;
ll mid = (l + r) / 2;
lft[mid] = en;
for (ll i=en;i>=st;i--){
// turn it on
insert(a[i], 1);
ll nw = get(max(mid - (S - i), 0LL));
if (SumL[mid] < nw)
SumL[mid] = nw, lft[mid] = i;
}
for (ll i=st;i<=lft[mid];i++)
insert(a[i], -1);
// turn some off
solve2(mid + 1, r, st, lft[mid], S);
for (ll i=lft[mid]+1;i<=en;i++)
insert(a[i], -1);
// turn remaining off
solve2(l, mid - 1, lft[mid], en, S);
}
bool flg;
long long findMaxAttraction(int n, int s, int d, int at[]){
// cout<<n<<" "<<s<<" "<<d<<endl;
s += !flg, cr = 0;
for (ll i=0;i<(N << 2);i++)
lft[i] = rgt[i] = SumL[i] = SumR[i] = 0;
for (ll i=1;i<=n;i++)
a[i] = at[i-1], mp[a[i]];
if (mp2.size() == 0){
for (auto [i, j] : mp)
mp2[i] = ++cr, rev[cr] = i;
}
for (ll i=1;i<=n;i++)
a[i] = mp2[a[i]];
solve1(0, d + 10, s, n, s);
if (s > 1)
solve2(0, d + 10, 1, s - 1, s - 1);
ll Max = 0;
for (ll i=0;i<=d;i++){
ll k = max(0LL, d - (rgt[i] - s) - i - 1);
Max = max(Max, SumR[i] + SumL[k]);
}
for (ll i=0;n - i - 1 > i;i++)
swap(at[i], at[n - i - 1]);
if (!flg)
flg = 1, Max = max(Max, findMaxAttraction(n, n - s + 1, d, at));
return Max;
}
