#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[1000001], suff[1000001];
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(int i=0;i<=n;i++)
{
ll res = pref[i-1];
// for(int j=i-1;j>=0;j-=k) res+=p[j]<<1;
int j;
for(j=i;j<n;j+=k)
{
if((p[j]<<1)>=len)
{
break;
}
res+=len;
}
res+=suff[j];
// for(;j<n;j+=k) res+=(len-p[j])<<1;
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
*/
