#include "boxes.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const ll MAX = 1e7+4, oo = 1e18;
ll dp[MAX];
int arr[MAX];
int n, k, s;
ll delivery(int N, int K, int L, int p[]){
n = N;
k = K;
s = L;
for(int i = 1; i <= n; i++) arr[i] = p[i - 1];
memset(dp, 0, sizeof(dp));
deque<int> dq1, dq2;
dq1.push_back(0);
dq2.push_back(0);
for(int i = 1; i <= n; i++){
dp[i] = min(dp[dq1[0]] + min(2 * arr[i], s), dp[dq2[0]] + 2 * (s - arr[dq2[0]+1]));
//
while(dq1.size() && dp[dq1.back()] > dp[i]) dq1.pop_back();
dq1.push_back(i);
if(dq1.front() == i - k) dq1.pop_front();
//
while(dq2.size() && dp[dq2.back()] - 2 * arr[dq2.back()+1] > dp[i] - 2 * arr[i+1]) dq2.pop_back();
dq2.push_back(i);
if(dq2.front() == i - k) dq2.pop_front();
}
return dp[n];
}
