#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
int n, k, l;
int dist(int a, int b) {
if (a > b) swap(a, b);
if (a == 0) return min(b, l - b);
return min(b - a, dist(0, a) + dist(0, b));
}
int delivery(int32_t N, int32_t K, int32_t L, int32_t p[]) {
n = N, k = K, l = L;
map<int, int> pos;
for (int i = 0; i < n; i++) pos[p[i]]++;
deque<pii> v = {{0, 0}};
for (auto [a, b] : pos) v.push_back({a, b});
v.push_back({0, 0});
int cval, ans, lst;
deque<pii> bv = v;
n = v.size();
// run one
v = bv;
cval = k, ans = 0;
lst = 0;
vector<int> pf(n), repf(n), pf2(n), arrPf(n);
for (int i = 0; i < n; i++) {
auto& [po, need] = v[i];
ans += dist(lst, po);
// get whatever is needed done in here
pf2[i] = ans;
arrPf[i] = cval;
repf[i] = max(0LL, need - cval);
while (need > cval) {
need -= cval;
ans += 2*dist(0, po);
cval = k;
}
cval -= need;
need = 0;
pf[i] = ans;
// go to next one
lst = po;
}
// run 2
v = bv;
vector<int> sf(n), resf(n), sf2(n), arrSf(n);
cval = k, ans = 0;
lst = 0;
for (int i = n - 1; i >= 0; i--) {
auto& [po, need] = v[i];
ans += dist(lst, po);
// get whatever is needed done in here
sf2[i] = ans;
arrSf[i] = cval;
resf[i] = max(0LL, need - cval);
while (need > cval) {
need -= cval;
ans += 2*dist(0, po);
cval = k;
}
cval -= need;
need = 0;
sf[i] = ans;
// go to next one
lst = po;
}
// calc ans for remaining stuff
int mians = min(pf[n - 1], sf[0]);
for (int i = 0; i < n; i++) {
int po = v[i].fr;
int qsf = 0, qpf = 0, nans = 0;
// did pf first, now sf
cval = arrSf[i]; // quando o sf tinha isso de cval
nans = pf2[i] + sf2[i] + 2*dist(v[i].fr, 0);
while (repf[i] > cval) {
repf[i] -= cval;
nans += 2*dist(0, po);
cval = k;
}
mians = min(mians, nans);
// did sf first, now pf
cval = arrPf[i]; // quando o pf tinha isso de cval
nans = pf2[i] + sf2[i] + 2*dist(v[i].fr, 0);
while (resf[i] > cval) {
resf[i] -= cval;
nans += 2*dist(0, po);
cval = k;
}
mians = min(mians, nans);
}
// calc ans
for (int i = 0; i < n; i++) {
if ((i + 1) < n) mians = min(mians, pf[i] + sf[i + 1] + dist(v[i].fr, 0) + dist(v[i + 1].fr, 0));
if (i > 0) mians = min(mians, pf[i - 1] + sf[i] + dist(v[i].fr, 0) + dist(v[i - 1].fr, 0));
}
// print
cout << mians << "\n";
return mians;
}
