#include"holiday.h"
//#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,D,pas,jm,n,RR,za,l,r,z,k;
//long long LF[300009][3],RG[300009][3];
vector <vector <long long> > LF,RG;
int f[100009],g[100009],T[100009],E;
map <int, int> M;
map <int, int>::iterator IT;
//vector <long long> pr[270009];
vector <long long> seg[270009];
vector <int> B[270009];
void upd(int q, int w, int rr){
if(q>w) return;
int mid=(q+w)/2;
B[rr].resize(seg[rr].size());//pr[rr].resize(seg[rr].size());
//for(int h=1; h<seg[rr].size(); h++) pr[rr][h]=pr[rr][h-1]+T[f[seg[rr][h]]];
if(q==w){
for(int h=1; h<seg[rr].size(); h++) seg[rr][h]=seg[rr][h-1]+T[f[seg[rr][h]]];
return;
}
seg[rr*2].push_back(0);seg[rr*2+1].push_back(0);
for(int h=1; h<seg[rr].size(); h++){
if(f[seg[rr][h]]<=mid){
seg[rr*2].push_back(seg[rr][h]);
B[rr][h]=B[rr][h-1]+1;
}else{
seg[rr*2+1].push_back(seg[rr][h]);
B[rr][h]=B[rr][h-1];
}
}
for(int h=1; h<seg[rr].size(); h++) seg[rr][h]=seg[rr][h-1]+T[f[seg[rr][h]]];
upd(q,mid,rr*2);
upd(mid+1,w,rr*2+1);
}
void wv(){
M.clear();
for(i=1; i<=a; i++) M[f[i]]=1;
zx=0;
for(IT=M.begin(); IT!=M.end(); IT++){
zx++;M[(*IT).first]=zx;T[zx]=(*IT).first;
}
for(i=1; i<=a; i++) f[i]=M[f[i]];
//
za=1;
while(za<a) za*=2;
for(i=0; i<=za*2; i++){
seg[i].clear();B[i].clear();//pr[i].clear();
}
seg[1].push_back(0);
for(i=1; i<=a; i++){
seg[1].push_back(i);
}
upd(1,a,1);
}
void read(int q, int w, int rr, int L, int R){
if(L>R||q>w||k<=0) return;
if(R==0||L==seg[rr].size()) return;
if(R-L+1<=k){
k-=R-L+1;
//z+=pr[rr][R]-pr[rr][L-1];
z+=seg[rr][R]-seg[rr][L-1];
return;
}
if(q==w){
z+=T[q]*k;
k=0;
return;
}
read((q+w)/2+1,w,rr*2+1,((L-1)-B[rr][L-1])+1,R-B[rr][R]);
read(q,(q+w)/2,rr*2,B[rr][L-1]+1,B[rr][R]);
}
void rec(int q, int w, int qq, int ww){
if(q>w) return;
int mid=(q+w)/2,we=0;
long long qw=0;
for(int h=qq; h<=ww; h++){
k=mid-(h-1)*RR;z=0;
if(k<=0) break;
read(1,a,1,1,h);
if(qw<z){
qw=z;we=h;
}
}
if(E==1) LF[mid][RR-1]=qw; else RG[mid][RR-1]=qw;
rec(q,mid-1,qq,we);
rec(mid+1,w,we,ww);
}
long long int findMaxAttraction(int Nn, int start, int Dd, int attraction[]) {
n=Nn;start++;D=Dd;a=n;
for(i=1; i<=n; i++){
g[i]=attraction[i-1];f[i]=g[i];
}
for(i=start; i<=n; i++){
f[i-start+1]=g[i];
}
zx=min(n-start+1,start-1LL);
RG.resize((n-start+1)*2+zx+2);LF.resize((start-1)*2+zx+2);
for(i=0; i<LF.size(); i++) LF[i].resize(2);
for(i=0; i<RG.size(); i++) RG[i].resize(2);
long long LEF=LF.size()-1,RIG=RG.size()-1;
a=n-start+1;RR=1;
wv();
rec(1,min(D,RIG),1,a);
RR=2;
rec(1,min(D,RIG),1,a);
if(start!=1){
E=1;
for(i=start-1; i>=1; i--){
f[start-1-i+1]=g[i];
}
a=start-1;RR=1;
wv();
rec(1,min(D,LEF),1,a);
RR=2;
rec(1,min(D,LEF),1,a);
}
//
if(start==1) return RG[min(D,RIG)][0];
pas=max(pas,RG[min(D,RIG)][0]);
for(i=0; i<=D; i++){
if(D-i-2>=0){
zx=LF[min(i,LEF)][1]+RG[min(D-i-2,RIG)][0];
pas=max(pas,zx);
}
if(D-i-1>=0){
zx=RG[min(i,RIG)][1]+LF[min(D-i-1,LEF)][0];
pas=max(pas,zx);
}
}
return pas;
}
