#include "boxes.h"
#include <iostream>
#include <assert.h>
#include <utility>
#include <algorithm>
#define ll long long
#define pii pair<ll, int>
#define fst first
#define snd second
const ll INF = 1e18;
using namespace std;
ll dp[10000001];
pii dq[10000001];
int LF = 0, RG = 0;
long long delivery(int N, int K, int L, int p[])
{
dp[0] = 0;
dq[RG++] = {dp[0] + 2 * (L - p[0]), 0};
for (int i = 1; i <= N; i++)
{
while (LF < RG && dq[LF].snd < i - K) {LF++;}
dp[i] = INF;
dp[i] = min(dp[i], dp[max(0, i - K)] + 2 * p[i - 1]);
dp[i] = min(dp[i], dp[max(0, i - K)] + L);
if (LF < RG) dp[i] = min(dp[i], dq[LF].fst);
while (LF < RG && dp[i] + 2 * (L - p[i]) <= dq[RG - 1].fst) {RG--;}
dq[RG++] = {dp[i] + 2 * (L - p[i]), i};
}
return dp[N];
}
