#include "boxes.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

typedef long long ll;

const int N = 1e7 + 7;

int n, k, l, p[N];
ll dp[N];

}

long long delivery(int grdn, int grdk, int grdl, int grdp[]) {
	n = grdn;
	k = grdk;
	l = grdl;
	for (int i = 0; i < n; ++i) {
		p[i] = grdp[i];
	}
	memset(dp, 0x3f, (n + 1) * sizeof dp[0]);
	dp[0] = 0;
	deque<int> q, q1;
	for (int i = 0; i < n; ++i) {
		while (!q.empty() && dp[q.back()] - 2 * p[q.back()] >= dp[i] - 2 * p[i]) {
			q.pop_back();
		}
		q.push_back(i);
		if (i - k >= 0 && q.front() == i - k) {
			q.pop_front();
		}
		while (!q1.empty() && dp[q1.back()] >= dp[i]) {
			q1.pop_back();
		}
		q1.push_back(i);
		if (i - k >= 0 && q1.front() == i - k) {
			q1.pop_front();
		}
		assert(!q.empty());
		assert(!q1.empty());
		assert(q.front() > i - k);
		assert(q1.front() > i - k);
		dp[i + 1] = min(dp[i + 1], dp[q.front()] + 2 * (l - p[q.front()]));
		dp[i + 1] = min(dp[i + 1], dp[q1.front()] + min(l, 2 * p[i]));
	}
	return dp[n];
	// for (int i = 0; i < n; ++i) {
	// 	for (int j = i; j < min(i + k, n); ++j) {
	// 		int cost = min({2 * p[j], 2 * (l - p[i]), l});
	// 		dp[j + 1] = min(dp[j + 1], dp[i] + cost);
	// 	}
	// }
	// return dp[n];
}