#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define num long long
vector<num> dp;
struct SegTree {
vector<num> tree;
int size, start, height;
SegTree (int _size) {
size = _size;
height = ceil(log2(size));
start = 1 << height;
tree.resize(start << 1);
}
void update (int index) {
if (index == 0) return ;
if (index < start) {
int n0 = index << 1;
int n1 = n0 + 1;
tree[index] = min(tree[n0], tree[n1]);
}
update(index >> 1);
}
void modify (int index, num value) {
tree[index + start] = value;
update(index + start);
}
num query (int l, int r) {
num res = 1e18;
l += start;
r += start;
while (l < r) {
if ((l & 1) == 1) res = min(res, tree[l]);
if ((r & 1) == 0) res = min(res, tree[r]);
l = (l + 1) >> 1;
r = (r - 1) >> 1;
}
if (l == r) res = min(res, tree[l]);
return res;
}
};
num valuation (int L, int P) {
return min(P, L - P);
}
long long delivery(int N, int K, int L, int p[]) {
sort(p, p + N);
SegTree opt(N + 1);
dp.resize(N + 1, 0);
dp[0] = 0;
opt.modify(0, valuation(L, p[0]) - p[0] + dp[0]);
dp[1] = valuation(L, p[0]) * 2;
opt.modify(1, valuation(L, p[1]) - p[1] + dp[1]);
for (int i = 2; i <= N; i ++) {
int pos = p[i - 1];
num mov = valuation(L, pos) + pos;
num mmv = opt.query(max(0, i - K), i - 1);
dp[i] = mmv + mov;
opt.modify(i, valuation(L, p[i]) - p[i] + dp[i]);
}
//for (int i = 0; i <= N; i ++)
// cout << dp[i] << " ";
//cout << endl;
return dp[N];
}
