#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000005
typedef long long ll;
ll pos[2*MAXN];
ll st[8*MAXN],lazy[8*MAXN];
int n,k;
ll l;
ll ans;
void update(int from,int to,ll val,int v=1,int start=0,int end=2*n-1){
if(start==from&&end==to){
lazy[v]+=val;
st[v]+=val;
return;
}
int mid=(start+end)/2;
if(lazy[v]){
//propagate
update(start,mid,lazy[v],2*v,start,mid);
update(mid+1,end,lazy[v],2*v+1,mid+1,end);
lazy[v]=0;
}
if(to<=mid){
update(from,to,val,2*v,start,mid);
}else if(from>mid){
update(from,to,val,2*v+1,mid+1,end);
}else{
update(from,mid,val,2*v,start,mid);
update(mid+1,to,val,2*v+1,mid+1,end);
}
st[v]=min(st[2*v],st[2*v+1]);
}
ll query(int from,int to,int v=1,int start=0,int end=2*n-1){
if(start==from&&end==to){
return st[v];
}
int mid=(start+end)/2;
if(lazy[v]){
//propagate
update(start,mid,lazy[v],2*v,start,mid);
update(mid+1,end,lazy[v],2*v+1,mid+1,end);
lazy[v]=0;
}
if(to<=mid){
return query(from,to,2*v,start,mid);
}else if(from>mid){
return query(from,to,2*v+1,mid+1,end);
}else{
return min(query(from,mid,2*v,start,mid),query(mid+1,to,2*v+1,mid+1,end));
}
}
ll dist(ll x){
return min(x,l-x);
}
int modn(int i){
return (i<n)?i:(i-n);
}
ll c(int i){
return dist(pos[modn(i)])+pos[i];
}
ll d(int i){
return dist(pos[modn(i+1)])-pos[i+1];
}
ll q(int s,int i){//dp[i] with start s
return c(i)+query(max(s,i-k),i-1);
}
ll dp(int i){
return query(i,i)-d(i);
}
long long delivery(int N, int K, int L, int positions[]) {
n=N;
k=K;
l=L;
if(N==1){
return 2*dist(positions[0]);
}
for(int i=0;i<n;i++){
pos[i]=positions[i];
}
for(int i=n;i<2*n;i++){
pos[i]=positions[i-n]+l;
}
update(0,0,2*dist(pos[0])+d(0));//base case
for(int i=1;i<n;i++){
update(i,i,q(0,i)+d(i));
}
ans=dp(n-1);
for(int s=1;s<n;s++){
update(s,s+n-2,2*dist(pos[s])-dp(s));
update(s+n-1,s+n-1,q(s,s+n-1)+d(s+n-1));//make dp[s+n-1]
ans=min(ans,dp(s+n-1));
}
return ans;
}
