#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int lef[1000010], righ[1000010], am[1000010];
ll val[1000010];
int upto;
void update(int node, int oldcurr, int curr, int cstart = 0, int cend = 1e9+10)
{
if (cstart == cend)
{
am[curr] = am[oldcurr]+1;
val[curr] = ((ll)am[curr]) * ((ll)cstart);
return;
}
int mid = (cstart+cend)/2;
if (node <= mid)
{
lef[curr] = ++upto;
righ[curr] = righ[oldcurr];
update(node, lef[oldcurr], lef[curr], cstart, mid);
}
else
{
righ[curr] = ++upto;
lef[curr] = lef[oldcurr];
update(node, righ[oldcurr], righ[curr], mid+1, cend);
}
am[curr] = am[lef[curr]] + am[righ[curr]];
val[curr] = val[lef[curr]] + val[righ[curr]];
}
ll query(int amt, int oldcurr, int curr, int cstart = 0, int cend = 1e9+10)
{
if (amt >= am[curr] - am[oldcurr]) return val[curr] - val[oldcurr];
else if (cstart == cend)
{
ll mult = min(amt, am[curr]-am[oldcurr]);
return mult*(ll)cstart;
}
int mid = (cstart+cend)/2;
if (am[righ[curr]] - am[righ[oldcurr]] >= amt)
{
return query(amt, righ[oldcurr], righ[curr], mid+1, cend);
}
else
{
int newam = amt - (am[righ[curr]] - am[righ[oldcurr]]);
ll val2 = val[righ[curr]] - val[righ[oldcurr]];
return val2 + query(newam, lef[oldcurr], lef[curr], cstart, mid);
}
}
int* rootat;
int otherarray[100010];
priority_queue<ll> pq;
ll mx;
ll findMaxAttraction2(int n, int start, int d, int attraction[]) {
assert(!start);
int at = d/2;
int moves = at*2-1;
ll sum = 0;
for (int i = 0; i < at; i++)
{
sum += attraction[i];
pq.push(-attraction[i]);
}
mx = sum;
for (int i = at; i < n; i++)
{
moves += 2;
pq.push(-attraction[i]);
sum += attraction[i];
while (moves > d && pq.size())
{
sum += pq.top();
pq.pop();
moves--;
}
//printf("%d %d\n", pq.size(), mx);
mx = max(mx, sum);
}
return mx;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
rootat = otherarray+1;
if (!start) return findMaxAttraction2(n, start, d, attraction);
for (int i = 0; i < n; i++)
{
rootat[i] = ++upto;
update(attraction[i], rootat[i-1], rootat[i]);
}
for (int s = 0; s <= start; s++)
{
int dist = start-s-1;
for (int e = s; e < n; e++)
{
dist++;
int allowed = d-dist;
if (allowed <= 0) continue;
ll sum = query(allowed, rootat[s-1], rootat[e]);
mx = max(mx, sum);
}
}
// printf("\n");
for (int e = start; e < n; e++)
{
int dist = e-start-1;
for (int s = e; s >= 0; s--)
{
dist++;
int allowed = d-dist;
if (allowed <= 0) continue;
ll sum = query(allowed, rootat[s-1], rootat[e]);
mx = max(mx, sum);
}
}
return mx;
}
