#include <bits/stdc++.h>
using namespace std;
using integer = int;
#define int long long
struct AIB///init(valorile posibile); update(val, fr) -> pune fr aparitii de val; query(k) -> suma celor mai mari k din structura
{
map<int, int> mp;
vector<int> rvalue;
int n;
vector<int> aib1, aib2;///aib1 -> cate <= i, aib2 -> suma rvalue a lor
void init(vector<int> values)
{
mp.clear();
rvalue.clear();
n = 0;
aib1.clear();
aib2.clear();
int psn = 0;
sort(values.begin(), values.end());
for (auto it : values)
{
if (!mp[it])
{
psn++;
mp[it] = psn;
}
}
n = psn;
aib1.resize(n + 1);
aib2.resize(n + 1);
rvalue.resize(n + 1);
for (auto it : values)
rvalue[mp[it]] = it;
}
int query1(int pos)
{
int rr = 0;
for (int i = pos; i > 0; i -= (i & -i))
rr += aib1[i];
return rr;
}
int query2(int pos)
{
int rr = 0;
for (int i = pos; i > 0; i -= (i & -i))
rr += aib2[i];
return rr;
}
void update(int val, int fr)
{
val = mp[val];
for (int i = val; i <= n; i += (i & -i))
{
aib1[i] += fr;
aib2[i] += fr * rvalue[val];
}
}
int query(int k)
{
if (query1(n) <= k)
return query2(n);
if (k <= 0)
return 0;
int sm_tot = query2(n);
int df = query1(n) - k;
int st = 0, pas = 1 << 18;
while (pas != 0)
{
if (st + pas <= n and aib1[st + pas] <= df)
{
sm_tot -= aib2[st + pas];
df -= aib1[st + pas];
st += pas;
}
pas /= 2;
}
if (df != 0)
{
st++;
sm_tot -= rvalue[st] * df;
}
return sm_tot;
}
};
int n, s, d, a[100005];
AIB ds;
int opt[100005], rsp[100005];
void divide(int l, int r, int st, int dr)
{
if (l > r)
return;
int mij = (l + r) / 2;
for (int i = r; i >= mij; i--)
ds.update(a[i], 1);
int bst = -1, unde;
for (int i = st; i <= dr; i++)
{
ds.update(a[i], 1);
int cr = ds.query(d - 2 * (s - mij) - (i - s));
if (cr > bst)
{
bst = cr;
unde = i;
}
}
opt[mij] = unde;
rsp[mij] = bst;
for (int i = dr; i >= st; i--)
ds.update(a[i], -1);
divide(l, mij - 1, st, opt[mij]);
for (int i = mij; i <= r; i++)
ds.update(a[i], -1);
divide(mij + 1, r, opt[mij], dr);
}
int solve()
{
vector<int> all_values;
for (int i = 1; i <= n; i++)
all_values.push_back(a[i]);
AIB ds_caz1;
ds_caz1.init(all_values);
int ans = 0;
for (int i = s; i <= n; i++)
{
ds_caz1.update(a[i], 1);
ans = max(ans, ds_caz1.query(d - (i - s)));
}
ds.init(all_values);
for (int i = 1; i <= n; i++)
opt[i] = 0;
if (s == 1 or s == n)
return ans;
ds.update(a[s], 1);
divide(1, s - 1, s + 1, n);
for (int i = 1; i < s; i++)
ans = max(ans, rsp[i]);
/*for (int l = 1; l < s; l++)
{
int bst = -1, ps;
for (int i = l; i < s; i++)
ds.update(a[i], 1);
for (int i = s; i <= n; i++)
{
ds.update(a[i], 1);
int cr = ds.query(d - (i - s) - 2 * (s - l));
if (cr > bst)
bst = cr, ps = i;
}
for (int i = l; i <= n; i++)
ds.update(a[i], -1);
opt[l] = ps;
if (l > 1 and opt[l] < opt[l - 1])
assert(false);
ans = max(ans, bst);
}*/
return ans;
}
long long findMaxAttraction(integer N, integer Start, integer D, integer Attraction[])
{
n = N;
s = Start + 1;
d = D;
for (int i = 1; i <= n; i++)
a[i] = Attraction[i - 1];
int ans = solve();
s = n - s + 1;
reverse(a + 1, a + n + 1);
ans = max(ans, solve());
return ans;
}
/*
5 2 7
10 2 20 30 1
*/
