#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
long long dp[1000100];
long long delivery(int N, int K, int L, int p[]) {
int mid = L/2;
int lstPos = -1;
for (int i = 1; i <= N; i++){
dp[i] = 1e18;
bool bb = 0;
int pos = p[i-1];
if (lstPos == -1 && pos >= L-mid)
lstPos = i;
int pos2 = p[max(0, i-K)];
if ((pos2 <= mid && pos <= mid) || (pos2 >= mid && pos >= mid) ){
dp[i] = min(dp[i], dp[max(0, i-K)] + max(min(pos2, L-pos2), min(pos, L-pos))*2 );
} else {
dp[i] = min(dp[i], dp[max(0, i-K)] + L);
dp[i] = min(dp[i], dp[lstPos-1] + max(min(p[lstPos-1], L-p[lstPos-1]), min(pos, L-pos))*2 );
}
//cout << i << ' ' << dp[i] << endl;
/*for (int j = 1; j <= K; j++){
if (i-j < 0)
break;
int pos2 = p[i-j];
if (mid != pos2 && mid != pos && (mid-pos2)/abs(mid-pos2) != (mid-pos)/abs(mid-pos) ){
bb = 1;
}
if (bb){
dp[i] = min(dp[i], dp[i-j] + L);
} else {
dp[i] = min(dp[i], dp[i-j] + max(min(pos2, L-pos2), min(pos, L-pos))*2);
}
}*/
}
long long ans = dp[N];
lstPos = -1;
dp[N+1] = 0;
for (int i = N; i >= 1; i--){
dp[i] = 1e18;
bool bb = 0;
int pos = p[i-1];
if (lstPos == -1 && pos <= mid)
lstPos = i;
int pos2 = p[min(N, i+K-1)-1];
if ((pos2 <= mid && pos <= mid) || (pos2 >= mid && pos >= mid) ){
dp[i] = min(dp[i], dp[min(N+1, i+K)] + max(min(pos2, L-pos2), min(pos, L-pos))*2 );
} else {
dp[i] = min(dp[i], dp[min(N+1, i+K)] + L);
dp[i] = min(dp[i], dp[lstPos+1] + max(min(p[lstPos-1], L-p[lstPos-1]), min(pos, L-pos))*2 );
}
/*for (int j = 1; j <= K; j++){
if (i-j < 0)
break;
int pos2 = p[i-j];
if (mid != pos2 && mid != pos && (mid-pos2)/abs(mid-pos2) != (mid-pos)/abs(mid-pos) ){
bb = 1;
}
if (bb){
dp[i] = min(dp[i], dp[i-j] + L);
} else {
dp[i] = min(dp[i], dp[i-j] + max(min(pos2, L-pos2), min(pos, L-pos))*2);
}
}*/
}
ans = min(ans, dp[1]);
return ans;
}
