#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define fi first
#define se second
typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, int> pli;
const int maxn = 3e5 + 5;
int si;
int a[maxn];
vector<int> vals;
int m;
pli f[maxn], g[maxn];
struct segment_tree
{
lli total[maxn * 4];
int cnt[maxn * 4];
void init()
{
fill(begin(total), end(total), 0);
fill(begin(cnt), end(cnt), 0);
}
void update(int x, int l, int r, int p, int k)
{
if(l == r)
{
total[x] += k * vals[l];
cnt[x] += k;
return;
}
int mid = (l + r) / 2;
if(p <= mid) update(x * 2, l, mid, p, k);
else update(x * 2 + 1, mid + 1, r, p, k);
total[x] = total[x * 2] + total[x * 2 + 1];
cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
}
lli get(int x, int l, int r, int k)
{
if(l == r) return vals[l] * 1LL * min(k, cnt[x]);
int mid = (l + r) / 2;
if(cnt[x * 2 + 1] <= k)
return total[x * 2 + 1] + get(x * 2, l, mid, k - cnt[x * 2 + 1]);
else return get(x * 2 + 1, mid + 1, r, k);
}
} tree;
lli query(int l, int r, int k, bool flag = false)
{
static int curl = 1, curr = 0;
if(flag)
{
curl = 1;
curr = 0;
tree.init();
return 0;
}
while(curr < r)
{
++curr;
tree.update(1, 0, m - 1, a[curr], 1);
}
while(curr > r)
{
tree.update(1, 0, m - 1, a[curr], -1);
--curr;
}
while(curl > l)
{
--curl;
tree.update(1, 0, m - 1, a[curl], 1);
}
while(curl < l)
{
tree.update(1, 0, m - 1, a[curl], -1);
++curl;
}
return tree.get(1, 0, m - 1, k);
}
void dnc_f(int l, int r, int optl, int optr)
{
if(l > r) return;
int mid = (l + r) / 2;
lli best = -1, opt = 0;
for(int i = optl; i <= min(mid, optr); ++i)
{
lli k = query(si, si + i, mid - i);
if(k > best)
{
best = k;
opt = i;
}
}
f[mid] = pli(best, si + opt);
dnc_f(l, mid - 1, optl, opt);
dnc_f(mid + 1, r, opt, optr);
}
void dnc_g(int l, int r, int optl, int optr)
{
if(l > r) return;
int mid = (l + r) / 2;
lli best = -1, opt = 0;
for(int i = optl; i <= min(mid, optr); ++i)
{
lli k = query(si - 1 - i, si - 1, mid - i);
if(k > best)
{
best = k;
opt = i;
}
}
g[mid] = pli(best, si - 1 - opt);
dnc_g(l, mid - 1, optl, opt);
dnc_g(mid + 1, r, opt, optr);
}
lli findMaxAttraction(int n, int start, int d, int attraction[])
{
si = start;
for(int i = 0; i < n; ++i)
{
a[i] = attraction[i];
vals.push_back(a[i]);
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
m = sz(vals);
for(int i = 0; i < n; ++i)
a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
dnc_f(0, d, 0, n - 1 - start);
if(start > 0)
dnc_g(0, d, 0, start - 1);
lli ans = 0;
for(int i = 0; i <= d; ++i)
{
lli total = f[i].fi;
if(start > 0)
{
int p = f[i].se;
int left = d - i - (p - (start - 1));
if(left >= 0)
total += g[left].fi;
}
assert(total >= f[i].fi);
ans = max(ans, total);
}
reverse(a, a + n);
si = start = n - start - 1;
query(1, 0, 0, true);
dnc_f(0, d, 0, n - 1 - start);
if(start > 0)
dnc_g(0, d, 0, start - 1);
for(int i = 0; i <= d; ++i)
{
lli total = f[i].fi;
if(start > 0)
{
int p = f[i].se;
int left = d - i - (p - (start - 1));
if(left >= 0)
total += g[left].fi;
}
assert(total >= f[i].fi);
ans = max(ans, total);
}
return ans;
}
