#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct perSegTree{
struct node{
int active;
int sum;
int l,r;
};
node *st;
int cr=0;
node def;
void makeKids(int ind, int l, int r){
if(l==r)
return;
if(st[ind].l==-1){
st[ind].l=++cr;
st[ind].r=++cr;
}
}
int cop(int ind){
st[++cr]=st[ind];
return cr;
}
perSegTree(int nodes){
st=new node[nodes];
def={0,0,-1,-1};
fill(st,st+nodes,def);
}
int update(int l, int r, int i, int val, int ind){
if(i<l||i>r)
return ind;
makeKids(ind,l,r);
ind = cop(ind);
if(l==r){
st[ind].active=1;
st[ind].sum=val;
return ind;
}
int mid = (l+r)/2;
st[ind].l=update(l,mid,i,val,st[ind].l);
st[ind].r=update(mid+1,r,i,val,st[ind].r);
st[ind].active=st[st[ind].l].active+st[st[ind].r].active;
st[ind].sum=st[st[ind].l].sum+st[st[ind].r].sum;
return ind;
}
array<int,2>query(int l, int r, int s, int e, int ind){
if(e<l||s>r)
return {0,0};
if(s<=l&&r<=e){
return {st[ind].active,st[ind].sum};
}
int mid = (l+r)/2;
array<int,2>lef = query(l,mid,s,e,st[ind].l);
array<int,2>rig = query(mid+1,r,s,e,st[ind].r);
return {lef[0]+rig[0],lef[1]+rig[1]};
}
};
int ans;
void findAns(int ll, int lr, int rl, int rr, perSegTree &seg, int d, int st, int inds[], int n){
if(lr<ll)
return;
int k = (ll+lr)/2;
int optval = 0;
int opt = -1;
for(int i = rl;i<=rr;i++){
int lef = 2*(st-k)+(i-st);
lef=d-lef;
if(lef<=0){
break;
}
int lo = 0;
int hi = n;
while(lo<hi){
int mid = (lo+hi)/2;
if(seg.query(0,n-1,k,i,inds[mid])[0]<lef){
lo=mid+1;
}
else{
hi=mid;
}
}
if(optval<seg.query(0,n-1,k,i,inds[lo])[1]){
optval=seg.query(0,n-1,k,i,inds[lo])[1];
opt=i;
}
}
if(opt==-1){
//impossible for this one
findAns(k+1,lr,rl,rr,seg,d,st,inds,n);
return;
}
ans=max(ans,optval);
if(ll!=lr){
findAns(ll,k-1,rl,opt,seg,d,st,inds,n);
findAns(k+1,lr,opt,rr,seg,d,st,inds,n);
}
}
void justLeft(perSegTree &seg, int start, int n, int d, int inds[]){
for(int i = 0;i<=start;i++){
int l = start-i+1;
if(l>d)
continue;
int lo = 0;
int hi = n;
while(lo<hi){
int mid = (lo+hi)/2;
if(seg.query(0,n-1,i,start,inds[mid])[0]<(d-l)){
lo=mid+1;
}
else{
hi=mid;
}
}
ans=max(ans,seg.query(0,n-1,i,start,inds[lo])[1]);
}
}
long long findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
ans=0;
perSegTree seg(1e8);
array<int,2>arr[n];
for(int i = 0;i<n;i++){
arr[i]={attraction[i],i};
}
sort(arr,arr+n);
reverse(arr,arr+n);
int inds[n+1];
inds[0]=0;
for(int i = 0;i<n;i++){
inds[i+1]=seg.update(0,n-1,arr[i][1],arr[i][0],inds[i]);
}
justLeft(seg,start,n,d, inds);
findAns(0,start,start,n-1,seg,d,start,inds,n);
reverse(attraction,attraction+n);
start=n-start-1;
seg = perSegTree(1e8);
for(int i = 0;i<n;i++){
arr[i]={attraction[i],i};
}
sort(arr,arr+n);
reverse(arr,arr+n);
inds[0]=0;
for(int i = 0;i<n;i++){
inds[i+1]=seg.update(0,n-1,arr[i][1],arr[i][0],inds[i]);
}
justLeft(seg,start,n,d, inds);
findAns(0,start,start,n-1,seg,d,start,inds,n);
return ans;
}
