#include <bits/stdc++.h>
#include "boxes.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 1e7 + 5;
const ll infinity = 1e18;
int n, k, l;
ll dpl[MAX_N], dpr[MAX_N];
void CalcL(vi &p) {
vi d = {0};
d.reserve(n + 1);
int ind = 0;
for (int i = 1; i <= n; i++) {
while (d[ind] < i - k) ind++;
dpl[i] = dpl[d[ind]];
dpl[i] += min<ll>(l, 2 * p[i]);
while (!d.empty() && dpl[d.back()] > dpl[i]) d.pop_back();
d.push_back(i);
}
}
void CalcR(vi &p) {
vi d = {n + 1};
d.reserve(n + 1);
int ind = 0;
for (int i = n; i >= 0; i--) {
while (d[ind] > i + k) ind++;
dpr[i] = dpr[d[ind]];
dpr[i] += min<ll>(l, 2 * (l - p[i]));
while (!d.empty() && dpr[d.back()] > dpr[i]) d.pop_back();
d.push_back(i);
}
}
long long delivery(int N, int K, int L, int P[]) {
n = N, k = K, l = L;
vi p(n + 1);
ll ans = infinity;
for (int i = 1; i <= n; i++) p[i] = P[i - 1];
CalcL(p), CalcR(p);
for (int ind = 1; ind <= n + 1; ind++) {
chkmin(ans, dpl[ind - 1] + dpr[ind]);
}
return ans;
}
//3 2 8
//1 2 5
