#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> ind2coord;
struct Node{
ll s,e,m;
ll num = 0;
ll sum = 0;
ll val = 0;
Node *l, *r;
Node(ll _s, ll _e, bool children = true){
s=_s;e=_e;
//cout<<"node "<<s<<' '<<e<<endl;
m=(s+e)/2;
if (s==e){
val=ind2coord[s];
return;
}
if (children){
l = new Node(s,m,true);
r = new Node(m+1,e,true);
}
}
ll query(ll k){
if (k<0){return 0;}
//k largest elements
if (s==e){
//assert(k<=num);
return min(k,num)*val;
}
if (r->num>=k){
return r->query(k);
} else {
return l->query(k-r->num) + r->sum;
}
}
Node* update(ll ind, bool on){
//cout<<s<<' '<<e<<endl;
Node* ans = new Node(s,e,false);
if (s==e){
if (on){
ans->num = num+1;
} else {
ans->num = max(0LL, num-1);
}
ans->sum = ans->val * ans->num;
return ans;
}
if (ind<=m){
//cout<<"left"<<endl;
ans->l = l->update(ind,on);
ans->r = r;
} else {
//cout<<"right"<<endl;
ans->l = l;
ans->r = r->update(ind,on);
}
ans->num = ans->l->num + ans->r->num;
ans->sum = ans->l->sum + ans->r->sum;
return ans;
}
};
struct PersistentSet{
vector<Node*> nodes;
PersistentSet(){
//cout<<"ic "<<ind2coord.size()<<endl;
nodes.push_back(new Node(0,ind2coord.size()-1));
}
void insert(ll val){
ll ind = lower_bound(ind2coord.begin(), ind2coord.end(), val)-ind2coord.begin();
nodes.push_back(nodes.back()->update(ind,true));
}
ll query(ll k, ll t){
return nodes[t]->query(k);
}
void clear(){
nodes.clear();
nodes.push_back(new Node(0,ind2coord.size()-1));
}
};
vector<ll> rvals;
vector<ll> lvals;
vector<ll> rvals2;
vector<ll> lvals2;
PersistentSet *ps;
void dnc(ll s, ll e, ll x, ll y, vector<ll> &vals, bool thereandback){
//cout<<s<<' '<<e<<' '<<x<<' '<<y<<endl;
// query s,e knowing optimum lies within range x,y
ll m = (s+e)/2;
ll mx = -1;
ll mxind = -1;
for (ll v = x; v<=y; v++){
ll test = ps->query(m-(thereandback?2*v:v),v+1);
if (test>mx){
mx=test;
mxind=v;
}
}
vals[m]=mx;
if (s<m){
dnc(s,m-1,x,mxind,vals,thereandback);
}
if (m<e){
dnc(m+1,e,mxind,y,vals,thereandback);
}
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
ind2coord.resize(n);
for (ll i = 0; i<n; i++){
ind2coord[i]=attraction[i];
}
sort(ind2coord.begin(),ind2coord.end());
ind2coord.erase(unique(ind2coord.begin(),ind2coord.end()),ind2coord.end());
//cout<<ind2coord.size()<<endl;
ps = new PersistentSet();
ps->clear();
for (ll i = start; i<n; i++){
ps->insert(attraction[i]);
}
lvals2.resize((n-start)*4);
dnc(0,(n-start)*4-1,0,n-1-start,lvals2,true);
/*for (ll i : lvals2){
cout<<i<<' ';
}cout<<endl;*/
ps->clear();
for (ll i = start+1; i<n; i++){
ps->insert(attraction[i]);
}
lvals.resize((n-(start+1))*2);
if (start+1<n){
dnc(0,(n-(start+1))*2-1,0,n-1-(start+1),lvals,false);
}
/*for (ll i : lvals){
cout<<i<<' ';
}cout<<endl;*/
ps->clear();
for (ll i = start; i>=0; i--){
ps->insert(attraction[i]);
}
rvals2.resize((start+1)*4);
dnc(0,(start+1)*4-1,0,start,rvals2,true);
/*for (ll i : rvals2){
cout<<i<<' ';
}cout<<endl;*/
ps->clear();
for (ll i = start-1; i>=0; i--){
ps->insert(attraction[i]);
}
rvals.resize((start)*2);
if (start-1>=0){
dnc(0,(start)*2-1,0,start-1,rvals,false);
}
/*for (ll i : rvals){
cout<<i<<' ';
}cout<<endl;*/
//go left then go right
ll mx = 0;
for (ll i = 0; i<d-1; i++){
// i left, d right
if (lvals2.size()>i&&rvals.size()>d-1-i)
mx=max(mx,lvals2[i]+rvals[d-1-i]);
if (rvals2.size()>i&&lvals.size()>d-1-i)
mx=max(mx,rvals2[i]+lvals[d-i-1]);
}
return mx;
}
