#include"holiday.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=1e5+5;
int N,niz[maxn],D,poc;
priority_queue<int> PQ;
ll suma,res=0;
int tsz=1;
struct pstslog{
int d[2]={0,0};
int br=0;
ll zbir=0;
} st[1500000];
int make(){
++tsz;
return tsz;
}
void add(int vred,int kol,int gde=1,int lc=1,int dc=(1<<30)){
// cout<<gde<<endl;
if(lc==dc){
//cout<<"DODAJ NA "<<vred<<" "<<kol<<endl;
st[gde].br+=kol;
st[gde].zbir=(ll)st[gde].br*lc;
return;
}
int sred=(lc+dc)/2;
if(vred<=sred){
// cout<<"LEFT"<<endl;
if(st[gde].d[0]==0)
st[gde].d[0]=make();
add(vred,kol,st[gde].d[0],lc,sred);
}
else{
// cout<<"RIGHT"<<endl;
if(st[gde].d[1]==0)
st[gde].d[1]=make();
add(vred,kol,st[gde].d[1],sred+1,dc);
}
int d0=st[gde].d[0];
int d1=st[gde].d[1];
st[gde].br=st[d0].br+st[d1].br;
st[gde].zbir=st[d0].zbir+st[d1].zbir;
return;
}
ll sumtop(int k,int gde=1){
if(gde==0 or k<=0)
return 0;
if(k>=st[gde].br)
return st[gde].zbir;
int d0=st[gde].d[0];
int d1=st[gde].d[1];
return sumtop(k,d1)+sumtop(k-st[d1].br,d0);
}
/*ll summaxk(int l,int r,int k){
while(PQ.size())
PQ.pop();
ll s=0;
for(int i=l;i<=r;i++){
s+=niz[i];
PQ.push(-niz[i]);
while(PQ.size()>k){
s+=PQ.top();
PQ.pop();
}
}
return s;
}*/
struct slog{
int l,r,m,poz;
ll v;
int lj,rj;
};
vector<slog> V,novi;
void update(int idx,ll vred,int j){
if(V[idx].v>=vred)
return;
V[idx].v=vred;
V[idx].poz=j;
res=max(res,vred);
}
void split(int idx){
slog a,b,x=V[idx];
a.l=x.l;
a.r=x.m-1;
a.m=(a.l+a.r)/2;
a.lj=x.lj;
a.rj=x.poz;
a.v=0;
a.poz=a.rj;
b.l=x.m+1;
b.r=x.r;
b.m=(b.l+b.r)/2;
b.lj=x.poz;
b.rj=x.rj;
b.v=0;
b.poz=b.rj;
if(a.l<=a.r)
novi.push_back(a);
if(b.l<=b.r)
novi.push_back(b);
}
vector<pair<pair<int,int>,pair<int,int>>> upiti;
void makeq(int idx){
for(int j=V[idx].lj;j<=V[idx].rj;j++){
int d=V[idx].m-j+min(poc-j,V[idx].m-poc);
if(d>=D)
continue;
int k=D-d;
upiti.push_back({{j,V[idx].m},{k,idx}});
}
}
int lb,rb;
void processq(pair<pair<int,int>,pair<int,int>> x){
int l=x.f.f;
int r=x.f.s;
while(lb<l){
add(niz[lb],-1);
lb++;
}
while(rb<=r){
add(niz[rb],1);
rb++;
}
int k=x.s.f;
int idx=x.s.s;
/*
cout<<"SEGMENTNO"<<endl;
for(int i=1;i<=tsz;i++){
cout<<i<<": "<<st[i].br<<" | "<<st[i].zbir<<" | "<<st[i].d[0]<<" "<<st[i].d[1]<<endl;
}
cout<<l<<" "<<r<<" "<<lb<<" "<<rb<<" "<<k<<endl;*/
ll v=sumtop(k);/*
cout<<v<<endl;
exit(0);*/
update(idx,v,l);
}
void makestep(){
upiti.clear();
for(int i=0;i<V.size();i++){
makeq(i);
}
if(upiti.size()==0){
V.clear();
return;
}
sort(upiti.begin(),upiti.end());
lb=rb=1;
for(auto x:upiti)
processq(x);
while(lb<rb){
add(niz[lb],-1);
lb++;
}
novi.clear();
for(int i=0;i<V.size();i++)
split(i);
V.clear();
V=novi;
}
long long int findMaxAttraction(int n, int start, int ddd, int attraction[]) {
N=n;
for(int i=1;i<=N;i++)
niz[i]=attraction[i-1];
D=ddd;
start++;
if(start==1){
for(int i=start;i>=1;i--){
suma=0;
while(PQ.size())
PQ.pop();
for(int j=i;j<start;j++){
suma+=niz[j];
PQ.push(-niz[j]);
}
for(int j=start;j<=N;j++){
int d=j-i+min(start-i,j-start);
if(d>=D)
break;
suma+=niz[j];
PQ.push(-niz[j]);
while(PQ.size()+d>D){
suma+=PQ.top();
PQ.pop();
}
res=max(res,suma);
}
}
return res;
}
poc=start;
slog a;
a.l=start;
a.r=N;
a.lj=1;
a.rj=start;
a.m=(a.l+a.r)/2;
a.poz=a.rj;
a.v=0;
V.push_back(a);
while(V.size()){
makestep();
}
return res;
}
