#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
#define F first
#define S second
using ll = long long;
using pii= pair<int,int>;
using pll= pair<ll,ll>;
int n,k,len,*p;
ll ans=LLONG_MAX;
ll pref[10000001], suff[10000001];
ll delivery(int _N, int _K, int _L, int _p[])
{
n=_N; k=_K; len=_L; p=_p;
ans=LLONG_MAX;
for(int i=0;i<n;i++) pref[i] = (p[i]<<1) + (i<k?0:pref[i-k]);
for(int i=n-1;i>=0;i--) suff[i] = ((len-p[i])<<1) + (i+k>n?0:suff[i+k]);
for(ll i=0;i<=n;i++)
{
ll res = (i==0?0:pref[i-1]);
ll j=i;
ll l=0,r=(n-i)/k+1,mid;
while(l<=r)
{
mid = (l+r)>>1;
//cerr<<mid<<"->"<<i+mid*k<<endl;
if(i+mid*k>=n or (p[i+mid*k]<<1)>=len) r=mid-1;
else
{
l=mid+1;
}
}
j = i+l*k;
//cerr<<l<<' '<<r<<endl;
/*for(j=i;j<n;j+=k)
{
if((p[j]<<1)>=len)
{
break;
}
res+=len;
}*/
//cerr<<res<<endl;
res+=suff[j];
//cerr<<res<<endl;
res+=(l*len);
//cerr<<i<<' '<<res<<' '<<j<<endl;
ans = min(res,ans);
}
return ans;
}
namespace n2
{
int n,k,len,*p;
ll ans=LLONG_MAX;
ll pref[1000001], suff[1000001];
ll delivery(int _N, int _K, int _L, int _p[])
{
ans=LLONG_MAX;
n=_N; k=_K; len=_L; p=_p;
for(int i=0;i<n;i++) pref[i] = (p[i]<<1) + (i<k?0:pref[i-k]);
for(int i=n-1;i>=0;i--) suff[i] = ((len-p[i])<<1) + (i+k>n?0:suff[i+k]);
for(int i=-1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
ans = min(ans, (i==-1?0:pref[i]) + suff[j] + (1LL*j-1-i-1+k)/k*len);
//cerr<<i<<' '<<j<<" - "<<pref[i]<<' '<<suff[j]<<' '<<(1LL*j-1-i-1+k)/k*len<<endl;
}
}
return ans;
}
}
/*
4 8 8
3 4 5 6
4 8 9
3 4 5 6
5 3 26
1 4 13 20 21
:32
5 4 10
4 5 7 8 9
:12
3 2 8
1 2 5
*/
