#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
// probably binary search?
ll n, k, l;
vl p;
vl nxt, prev;
ll sim_dist(ll p1, ll p2) {
ll lmoves = 0, rmoves = 0;
ll lpos = p1, rpos = p1;
while (lpos != p2) {
lpos--;
if (lpos < 0) lpos = l - 1;
lmoves++;
}
while (rpos != p2) {
rpos++;
if (rpos >= l) rpos = 0;
rmoves++;
}
return min(lmoves, rmoves);
}
ll dist(ll p1, ll p2) {
if (p1 == p2) return 0;
if (p1 < p2) return dist(p2, p1);
else return min(p1 - p2, (l - p1) + p2);
}
// going left for kL teams and coming back
ll sim_left(ll kL) {
ll ansL = 0, pL = 0;
FOR(i, 0, kL) {
ll pidx = n - ll(i) - 1;
if (pL == 0) ansL += l - p[pidx];
else ansL += pL - p[pidx];
pL = p[pidx];
}
ansL += sim_dist(pL, 0);
return ansL;
}
// going right for kR teams and coming back
ll sim_right(ll kR) {
ll ansR = 0, pR = 0;
FOR(i, 0, kR) {
ll pidx = 0 + i;
ansR += p[pidx] - pR;
pR = p[pidx];
}
ansR += sim_dist(pR, 0);
return ansR;
}
ll delivery(int N, int K, int L, int P[]) {
n = N, k = K, l = L;
FOR(i, 0, n) p.pb(P[i]);
srt(p);
ll lo = 0, hi = n;
while (lo < hi) {
ll mid = lo + (hi - lo) / 2;
ll kL = mid, kR = n - mid;
ll ans = sim_left(kL) + sim_right(kR);
ll ans2 = sim_left(kL + 1) + sim_right(kR - 1);
if (ans < ans2) {
hi = mid;
} else {
lo = mid + 1;
}
}
return sim_left(lo) + sim_right(lo);
// return min(*max_element(all(p)) + dist(*max_element(all(p)), 0), l - *min_element(all(p)) + dist(*min_element(all(p)), 0));
// ll max_pos = *max_element(all(p));
// ll min_pos = *min_element(all(p));
// ll min_dist = dist(min_pos, l);
// return min({l, 2LL * max_pos, 2LL * min_dist});
}
