#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
long long seg[400005], cnt[400005], f[250005], ff[250005], g[250005], gg[250005], a[100005], c[100005], n, s, d, ans;
pair<long long, long long> b[100005];
void update(long long i, long long l, long long r, long long x, long long y)
{
// cout << "update " << i << ' ' << l << ' ' << r << ' ' << x << ' ' << y << '\n';
if (l==r)
{
seg[i]=y;
cnt[i]=(bool)y;
return;
}
long long mid=(l+r)/2;
if (x<=mid)
update(i*2, l, mid, x, y);
else
update(i*2+1, mid+1, r, x, y);
seg[i]=seg[i*2]+seg[i*2+1];
cnt[i]=cnt[i*2]+cnt[i*2+1];
}
long long query(long long i, long long l, long long r, long long x)
{
// cout << "query " << i << ' ' << l << ' ' << r << ' ' << x << '\n';
if (cnt[i]==x)
return seg[i];
long long mid=(l+r)/2;
if (cnt[i*2]>=x)
return query(i*2, l, mid, x);
else
return query(i*2, l, mid, cnt[i*2])+query(i*2+1, mid+1, r, x-cnt[i*2]);
}
long long query2(long long i, long long l, long long r, long long x)
{
// cout << "query2 " << i << ' ' << l << ' ' << r << ' ' << x << '\n';
if (cnt[i]==x)
return seg[i];
long long mid=(l+r)/2;
if (cnt[i*2+1]>=x)
return query2(i*2+1, mid+1, r, x);
else
return query2(i*2, l, mid, x-cnt[i*2+1])+query2(i*2+1, mid+1, r, cnt[i*2+1]);
}
void recur(long long l, long long r, long long ql, long long qr)
{
// cout << "recur " << l << ' ' << r << ' ' << ql << ' ' << qr << '\n';
long long mid=(l+r)/2;
for (long long i=ql; i<=qr; i++)
{
update(1, s, n-1, c[i], a[i]);
if (1<=mid-i+s)
{
long long res=query(1, s, n-1, min(cnt[1], mid-i+s));
if (ff[mid]<res)
{
ff[mid]=res;
f[mid]=i;
}
}
}
for (long long i=ql; i<=qr; i++)
update(1, s, n-1, c[i], 0);
if (l<mid)
recur(l, mid-1, ql, f[mid]);
if (mid<r)
recur(mid+1, r, f[mid], qr);
for (long long i=ql; i<=qr; i++)
update(1, s, n-1, c[i], a[i]);
}
void recur2(long long l, long long r, long long ql, long long qr)
{
// cout << "recur2 " << l << ' ' << r << ' ' << ql << ' ' << qr << '\n';
long long mid=(l+r)/2;
for (long long i=qr; i>=ql; i--)
{
update(1, 0, s-1, c[i], a[i]);
if (1<=mid-s+i+1)
{
long long res=query2(1, 0, s-1, min(cnt[1], mid-s+i+1));
if (gg[mid]<res)
{
gg[mid]=res;
g[mid]=i;
}
}
}
for (long long i=qr; i>=ql; i--)
update(1, 0, s-1, c[i], 0);
if (l<mid)
recur2(l, mid-1, g[mid], qr);
if (mid<r)
recur2(mid+1, r, ql, g[mid]);
for (long long i=qr; i>=ql; i--)
update(1, 0, s-1, c[i], a[i]);
}
long long findMaxAttraction(int N, int S, int D, int A[])
{
if (!D)
return 0;
n=N;
s=S;
d=D;
for (long long i=0; i<n; i++)
{
a[i]=A[i];
b[i]={a[i], i};
}
sort(b, b+s);
sort(b+s, b+n, greater<pair<long long, long long> >());
for (long long i=0; i<n; i++)
c[b[i].second]=i;
for (long long i=0; i<=d; i++)
{
f[i]=s;
g[i]=s-1;
}
if (s<n)
recur(1, d, s, n-1);
for (long long i=0; i<=4e5; i++)
seg[i]=cnt[i]=0;
if (s)
recur2(1, d, 0, s-1);
// cout << "f: ";
// for (long long i=0; i<=d; i++)
// cout << f[i] << ' ';
// cout << '\n';
// cout << "ff: ";
// for (long long i=0; i<=d; i++)
// cout << ff[i] << ' ';
// cout << '\n';
// cout << "g: ";
// for (long long i=0; i<=d; i++)
// cout << g[i] << ' ';
// cout << '\n';
// cout << "gg: ";
// for (long long i=0; i<=d; i++)
// cout << gg[i] << ' ';
// cout << '\n';
ans=max(ff[d], gg[d-1]);
for (long long i=0; i<=d; i++)
{
if (d-i-f[i]+s-1>=0)
ans=max(ans, ff[i]+gg[d-i-f[i]+s-1]);
if (d-i-s+g[i]-1>=0)
ans=max(ans, gg[i]+ff[d-i-s+g[i]-1]);
}
return ans;
}
