#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=19,kaf=(1<<lg);
long long all[maxn],n,st,k,allind[maxn];
long long mainres=0;
struct segment{
long long seg[(1<<(lg+1))];
void upd(long long i,long long w){
i+=kaf;
while(i>0){
seg[i]+=w;
i>>=1;
}
return ;
}
long long pors(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
if(l>=tl&&r<=tr){
return seg[i];
}
long long m=(l+r)>>1;
return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
}
long long porsakh(long long i,long long l,long long r,long long w){
if(l>r||seg[i]<w){
return -1;
}
if(l==r){
return l;
}
long long m=(l+r)>>1;
if(seg[(i<<1)^1]>=w){
return porsakh((i<<1)^1,m+1,r,w);
}
return porsakh((i<<1),l,m,w-seg[(i<<1)^1]);
}
}seg1,seg2;
void ins(int l,int r,int w){
for(int i=l;i<=r;i++){
seg1.upd(allind[i],w*all[i]);
seg2.upd(allind[i],w);
}
}
void solve(long long l,long long r,long long tl,long long tr){
if(l>r){
return ;
}
long long mid=(l+r)>>1,opt=tl,mx=-1;
ins(max(l,tr+1),mid,1);
for(long long i=tr;i>=tl;i--){
seg2.upd(allind[i],1);
seg1.upd(allind[i],all[i]);
long long ted=k-(mid-i+min(mid-st,st-i));
long long z=seg2.porsakh(1,0,kaf-1,ted);
long long fake=seg1.pors(1,0,kaf-1,z,n+1);
if(fake>mx){
mx=fake;
opt=i;
}
}
for(long long i=l;i<=mid;i++){
seg1.upd(allind[i],-all[i]);
seg2.upd(allind[i],-1);
}
for(long long i=tr;i>=tl;i--){
seg2.upd(allind[i],-1);
seg1.upd(allind[i],-all[i]);
}
mainres=max(mainres,mx);
for(long long i=opt+1;i<=tr;i++){
seg1.upd(allind[i],all[i]);
seg2.upd(allind[i],1);
}
solve(l,mid-1,tl,opt);
for(long long i=opt+1;i<=tr;i++){
seg1.upd(allind[i],-all[i]);
seg2.upd(allind[i],-1);
}
for(long long i=l;i<=mid;i++){
seg1.upd(allind[i],all[i]);
seg2.upd(allind[i],1);
}
solve(mid+1,r,opt,tr);
for(long long i=l;i<=mid;i++){
seg1.upd(allind[i],-all[i]);
seg2.upd(allind[i],-1);
}
}
long long findMaxAttraction(int N,int start,int d,int attraction[]) {
n=N;
st=start;
k=d;
st++;
vector<pair<long long ,long long>>comper;
for(long long i=1;i<=n;i++){
all[i]=attraction[i-1];
comper.push_back(make_pair(all[i],i));
}
sort(comper.begin(),comper.end());
comper.resize(unique(comper.begin(),comper.end())-comper.begin());
for(long long i=1;i<=n;i++){
allind[i]=lower_bound(comper.begin(),comper.end(),make_pair(all[i],i))-comper.begin();
}
solve(st,n,1,st);
return mainres;
}
