#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 = 1e6 + 5;
const ll infinity = 1e18;
//ll dp[MAX_N];
//ll Solve(vi &p, int l) {
// int n = p.size();
// ll ans = l;
// sort(all(p));
// for (int i = 0; i < n - 1; i++) {
// chkmin(ans, ll(2) * (p[i] + (l - p[i + 1])));
// }
// chkmin(ans, ll(2) * p[n - 1]);
// chkmin(ans, ll(2) * (l - p[0]));
// return ans;
//}
int n, k, l;
ll dp[MAX_N];
ll Solve(int ind, vi &p) {
ll ans = 0;
for (int i = 1; i < ind; i++) {
dp[i] = dp[i - 1];
int m = max(0, i - k);
for (int j = i - 1; j >= m; j--) {
chkmin(dp[i], dp[j]);
}
dp[i] += min<ll>(l, 2 * p[i]);
// int r = min(i + k, ind);
// ans += min<ll>(l, 2 * p[r - 1]);
}
for (int i = n; i >= ind; i--) {
dp[i] = dp[i + 1];
int m = min(n + 1, i + k);
for (int j = i + 1; j <= m; j++) {
chkmin(dp[i], dp[j]);
}
dp[i] += min<ll>(l, 2 * (l - p[i]));
// int left = max(ind, i - k + 1);
// ans += min<ll>(l, 2 * (l - p[left]));
}
return dp[ind - 1] + dp[ind];
}
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];
for (int ind = 1; ind <= n + 1; ind++) {
chkmin(ans, Solve(ind, p));
}
// sort(p, p + n);
// for (int i = 0; i < n; i++) {
// vi curr;
// dp[i] = infinity;
// for (int j = i; j >= 0; j--) {
// curr.push_back(p[j]);
// if (curr.size() > k) break;
// ll x = (j > 0 ? dp[j - 1] : 0);
// chkmin(dp[i], x + Solve(curr, l));
// }
// }
// chkmin(ans, dp[n - 1]);
return ans;
}
//3 2 8
//1 2 5
