#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define int long long
int INF = 1LL<<60;
//method:
//consider only going right, we'll try to compute the max obtainable with d days going to the right for each d
//now, let k be the number of cities we ever visit, and thus we get to actually see attractions of d-k cities
//we obviously visit the d-k cities with maximum attraction counts
//let visit(k,d) = max sum of visits for d with visiting the first k cities and actually opening d-k of them
//let opk[d] be the optimal number of cities to visit for d days
//note that opk[d+1]>=opk[d] (proved on paper)
//thus, for each d, there's a minimum k such that visit(k,d)<=visit(k+1,d), and from now we can use k+1 instead
//so binary search on this minimum k
//ok but we can't binary search this way round since that leads to too many insertions and erasures
//so we need to do a binary search on, for each k, the minimum d such that visit(k,d)<=visit(k+1,d)
//to do this, we need a data structure that can insert values, also query the sum of the maximum t values for any t
//this can be done with a segment tree of suffix sums with lazy propagation with coordinate compression
//since we know all the attraction values in advance
//keep a PBDS of what values are currently in the set
const int sz = 262144;
vector<int> revcoords;
class SegmentTree {
public:
vector<int> tree;
int n;
ordered_set current_indices;
SegmentTree(int numelem) {
tree=vector<int>(sz,0);
n=numelem;
//cout << "making segtree " << n << endl;
}
void update(int v, int l, int r, int tl, int tr, int addend) {
if (l>tr || r<tl) return;
if (l<=tl && tr<=r) {
assert(l==r);
tree[v]+=addend;
return;
}
int m = (tl+tr)/2;
update(2*v,l,r,tl,m,addend);
update(2*v+1,l,r,m+1,tr,addend);
tree[v] = tree[2*v]+tree[2*v+1];
}
int query(int v, int l, int r, int tl, int tr) {
if (l>tr || r<tl) return 0;
if (l<=tl && tr<=r) {
//cout << "qend " << tl <<" " << tr <<" " << tree[v] << endl;
return tree[v];
}
int m = (tl+tr)/2;
return query(2*v,l,r,tl,m)+query(2*v+1,l,r,m+1,tr);
}
void ins(int index, int weight) {
//weight must be weights[index]
int rc = revcoords[index];
current_indices.insert(rc);
//cout << "updating " << rc <<" " << weight << endl;
update(1,rc,rc,0,131071,weight);
}
void era(int index, int weight) {
//weight must be weights[index]
int rc = revcoords[index];
current_indices.erase(rc);
update(1,rc,rc,0,131071,-weight);
}
int get_sum_maximals(int k) {
//(1 indexed, so k=1 means you just want max etc)
if (current_indices.size()<k) {
return tree[1]; //sum of everything
}
if (k<=0) return 0;
int reqcid = current_indices.size();
reqcid-=k;
int req_index = *current_indices.find_by_order(reqcid);
int ans = query(1,req_index,131071,0,131071);
//cout << "getting " << k <<" " << current_indices.size() <<" " << reqcid <<" " << req_index << " " << ans << endl;
return ans;
}
};
vector<int> solve_for_all_d(int n, vector<int> weights) {
//ignore the middle itself
revcoords=vector<int>(n,-1);
vector<int> coords(n); iota(coords.begin(), coords.end(), (int)0);
for (int i=0; i<n; i++) {
//cout << weights[i] <<" ";
}
//cout << endl << endl;
sort(coords.begin(), coords.end(),[&](const int i1, const int i2) {
return weights[i1]<weights[i2];
});
for (int i=0; i<coords.size(); i++) {
//revcoords is what position this index takes in the sorted list by weight
revcoords[coords[i]] = i;
}
SegmentTree st(n);
SegmentTree st2(n);
vector<int> firstpoint(n,-1);
//thus, for each d, there's a minimum k such that visit(k,d)<=visit(k+1,d), and from now we can use k+1 instead
//so binary search on this minimum k
//ok but we can't binary search this way round since that leads to too many insertions and erasures
//so we need to do a binary search on, for each k, the minimum d such that visit(k-1,d)<=visit(k,d)
st.ins(0,weights[0]);
firstpoint[0] = 2;
int lastopt = 0;
int lastval = 2;
for (int k=1; k<n; k++) {
st.ins(k,weights[k]);
st2.ins(k-1,weights[k-1]);
int l = k+1;
int r = 8*n+8;
while (l<r) {
int m = (l+r)/2;
int rem1 = m-k-2;
int rem2 = m-k-1;
//cout << l <<" " << r <<" " << rem1 <<" " << rem2 <<" " << st.get_sum_maximals(rem1) <<" " << st2.get_sum_maximals(rem2) << endl;
if (st.get_sum_maximals(rem1)>=st2.get_sum_maximals(rem2)) {
//visit(k,d)>=visit(k-1,d), k is better, so binsearch down
l=l;
r=m;
}
else {
l=m+1;
r=r;
}
}
firstpoint[k] = l;
}
vector<int> suffmin(n,INF);
suffmin[n-1] = firstpoint[n-1];
for (int i=n-2; i>=0; i--) {
suffmin[i] = min(suffmin[i+1],firstpoint[i]);
}
for (int i=0; i<n; i++) {
//cout << "fsf " << i <<" " << firstpoint[i] << " " << suffmin[i] << endl;
}
vector<int> dans(2*n+1,0);
int pointer = 0;
SegmentTree st3(n);
for (int d=0; d<=2*n; d++) {
while (pointer<n && d>=suffmin[pointer]) {
st3.ins(pointer,weights[pointer]);
pointer++;
}
int rem = d-pointer;
dans[d] = st3.get_sum_maximals(rem);
//cout << d <<" " << dans[d] << " " << pointer << " " << firstpoint[pointer] <<" " << rem << endl;
}
return dans;
}
long long findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
vector<int> right;
for (int i=start; i<n; i++) {
right.push_back(attraction[i]);
}
vector<int> right_ans = solve_for_all_d(right.size(), right);
return right_ans[d+1];
}
