#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
#define mp make_pair
typedef long long llo;
#include"holiday.h"
llo it[100001];
llo n;
llo d;
llo ans=0;
llo ii;
llo tree[100000*40][2];
llo ll[100000*40][2];
llo rr[100000*40][2];
llo ind[1000001];
llo co[2];
llo cur[2];
vector<llo> rr3;
vector<llo> rr2;
llo update(llo no,llo l,llo r,llo i,llo val,llo tt){
llo ac=co[tt];
co[tt]++;
tree[ac][tt]=tree[no][tt];
ll[ac][tt]=ll[no][tt];
rr[ac][tt]=rr[no][tt];
if(l==r){
tree[ac][tt]+=val;
return ac;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
ll[ac][tt]=update(ll[ac][tt],l,mid,i,val,tt);
}
else{
rr[ac][tt]=update(rr[ac][tt],mid+1,r,i,val,tt);
}
tree[ac][tt]=tree[ll[ac][tt]][tt]+tree[rr[ac][tt]][tt];
return ac;
}
}
llo xy=0;
llo query(llo no,llo no2,llo l,llo r,llo k){
/* if(xy){
cout<<no<<",,"<<no2<<",,"<<l<<",,"<<r<<",,"<<k<<endl;
}*/
if(l==r){
return l;
//if(tree[no2]-tree[no]==)
}
else{
llo mid=(l+r)/2;
if(tree[ll[no2][0]][0]-tree[ll[no][0]][0]<k){
return query(rr[no][0],rr[no2][0],mid+1,r,k-(tree[ll[no2][0]][0]-tree[ll[no][0]][0]));
}
else{
return query(ll[no][0],ll[no2][0],l,mid,k);
}
}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree[no][1];
}
else{
llo mid=(l+r)/2;
return query2(ll[no][1],l,mid,aa,bb)+query2(rr[no][1],mid+1,r,aa,bb);
}
}
void solve(llo l,llo r,llo aa,llo bb){
llo mid=(l+r)/2;
pair<llo,llo> cur={0,aa};
for(llo x=aa;x<=bb;x++){
llo le=d-2*(ii-mid)-(x-ii);
//mid to x range
if(le>0){
llo zz;
/* if(mid==1 and x==4){
xy=1;
cout<<le<<")"<<endl;
}*/
/* vector<llo> xx2;
for(llo k=mid;k<=x;k++){
xx2.pb(it[k]);
}
sort(xx2.begin(),xx2.end());
*/
llo su=0;
/* for(llo i=0;i<xx2.size();i++){
if(i+1>le){
break;
}
su+=xx2[i];
}*/
if(le<x-mid+1){
zz=query(rr3[mid],rr3[x+1],0,n-1,le);
}
else{
zz=n;
}
// xy=0;
su=query2(rr2[zz+1],0,n-1,mid,x);
/* if(mid==1 and x==4){
cout<<le<<")"<<zz<<"<"<<su<<endl;
}*/
if(su<cur.a){
cur={su,x};
}
}
}
// cout<<mid<<":"<<cur.a<<":"<<cur.b<<endl;
ans=min(ans,cur.a);
if(mid>l){
solve(l,mid-1,aa,cur.b);
}
if(mid<r){
solve(mid+1,r,cur.b,bb);
}
}
void solve(llo i){
multiset<llo> ss;
ii=i;
llo su=0;
for(llo j=i;j>=0;j--){
if(i-j>d){
break;
}
ss.insert(it[j]);
su+=it[j];
while(ss.size()>d-(i-j) and ss.size()>0){
auto j=ss.end();
j--;
su-=(*j);
ss.erase(j);
}
ans=min(ans,su);
}
if(i==0 or i==n-1){
return;
}
/* for(llo j=0;j<n;j++){
cout<<it[j]<<" ";
}
cout<<endl;
cout<<i<<".."<<endl;*/
vector<pair<llo,llo>> val;
for(llo j=0;j<n;j++){
val.pb({it[j],j});
}
sort(val.begin(),val.end());
for(llo k=0;k<2;k++){
co[k]=0;
for(llo j=0;j<2*n;j++){
tree[j][k]=0;
ll[j][k]=j*2+1;
rr[j][k]=j*2+2;
co[k]=max(co[k],rr[j][k]+1);
}
}
rr3.clear();
rr2.clear();
rr3.pb(0);
cur[0]=0;
cur[1]=0;
for(llo j=0;j<n;j++){
ind[val[j].b]=j;
}
for(llo j=0;j<n;j++){
cur[0]=update(cur[0],0,n-1,ind[j],1,0);
rr3.pb(cur[0]);
}
rr2.pb(0);
for(llo j=0;j<n;j++){
cur[1]=update(cur[1],0,n-1,val[j].b,val[j].a,1);
rr2.pb(cur[1]);
// cout<<val[j].a<<"...."<<val[j].b<<endl;
}
//return ;
llo l=i;
while(l>0){
if((i-(l-1))*2<=d){
l--;
}
else{
break;
}
}
if(i==0 or i==n-1){
return;
}
// return ;
solve(l,i,i,n-1);
}
llo findMaxAttraction(int nn, int start, int dd, int at[]) {
n=nn;
d=dd;
ans=0;
for(llo i=0;i<n;i++){
it[i]=-at[i];
}
solve(start);
for(llo i=0;i<n/2;i++){
swap(it[i],it[n-i-1]);
}
solve(n-start-1);
return -ans;
}
