#include"holiday.h"
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
typedef long long ll;
const int maxd=2.5e5+10;
int siz=0;
void add(int t,int v,vector<pair<ll,ll> > &segt,int ind=1,int l=0,int r=siz){
if(l==r){
segt[ind].xx+=v;
if(segt[ind].xx==0) segt[ind].yy=0;
else segt[ind].yy=1;
return;
}
int mid=l+(r-l)/2;
if(t<=mid) add(t,v,segt,2*ind,l,mid);
else add(t,v,segt,2*ind+1,mid+1,r);
segt[ind].xx=segt[2*ind].xx+segt[2*ind+1].xx;
segt[ind].yy=segt[2*ind].yy+segt[2*ind+1].yy;
}
ll query(int t,vector<pair<ll,ll> > &segt,int ind=1,int l=0,int r=siz){
int mid=l+(r-l)/2;
ll ret=0;
if(segt[ind].yy<=t) return segt[ind].xx;
ret+=query(min(segt[2*ind].yy,ll(t)),segt,2*ind,l,mid);
if(segt[2*ind].yy<t) ret+=query(t-segt[2*ind].yy,segt,2*ind+1,mid+1,r);
return ret;
}
void dc(int l,int r,int bl,int br,vector<pair<int,int> > &atr,vector<int> &where,vector<ll> &res,vector<pair<ll,ll> > &segt){
if(l>r) return;
int mid=l+(r-l)/2;
int b=0,bpos=bl;
for(int i=bl;i<=br;i++){
add(where[i],atr[where[i]].xx,segt);
if(i>=mid) continue;
int q=0;
if((q=query(mid-i,segt))>b){
b=q;
bpos=i;
}
}
res[mid]=b;
for(int i=bpos;i<=br;i++) add(where[i],-atr[where[i]].xx,segt);
dc(mid+1,r,bpos,br,atr,where,res,segt);
for(int i=bl;i<bpos;i++) add(where[i],-atr[where[i]].xx,segt);
dc(l,mid-1,bl,bpos,atr,where,res,segt);
}
void solve(vector<pair<int,int> > &atr,vector<ll> &res,int d){
if(atr.empty()) return;
vector<int> where(atr.size());
for(int i=0;i<atr.size();i++) where[atr[i].yy]=i;
vector<pair<ll,ll> > segt(4*atr.size()+10);
siz=atr.size()-1;
dc(0,d,0,atr.size()-1,atr,where,res,segt);
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<pair<int,int> > left,right;
vector<ll> rleft(d+1),rright(d+1);
for(int i=0;i<n;i++){
if(i<start) left.push_back(make_pair(attraction[i],start-i-1));
else right.push_back(make_pair(attraction[i],i-start));
}
sort(left.begin(),left.end(),greater<pair<int,int> >()); sort(right.begin(),right.end(),greater<pair<int,int> >());
solve(right,rright,d);
solve(left,rleft,d);
return rright[d];
}
/*
100 0 150
4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13
*/
