#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000005
typedef long long ll;
ll pos[MAXN];
deque<pair<int,ll>> min_q;
int n,k;
ll l;
ll ans;
ll min_(){
return min_q.front().second;
}
void insert_q(pair<int,ll> p){
while(!min_q.empty()&&p.second<min_q.back().second) min_q.pop_back();
min_q.push_back(p);
}
void erase_q(int x){
if(!min_q.empty()&&min_q.front().first==x) min_q.pop_front();
}
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];
}
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=1;i<=n;i++){
pos[i]=positions[i-1];
}
insert_q({0,d(0)});//base case
for(int i=1;i<=n;i++){
erase_q(i-k-1);
ans=min_()+c(i);
insert_q({i,min_()+c(i)+d(i)});
}
return ans;
}
