#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll B = 2305843009213693951;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
// ll delivery(int n, int k, int l, int p[]) {
// int a = 0, b = l;
// for (ll i = 0; i < n; i++) {
// if (p[i] <= l / 2) a = max(a, p[i]);
// else b = min(b, p[i]);
// }
// ll res = min(l, 2 * (a + (l - b)));
// return res;
// }
ll mod(ll x, ll k) {
return ((x % k) + k) % k;
}
ll delivery(int n, int k, int l, int p[]) {
unordered_map<ll, ll> mp;
for (ll i = 0; i < n; i++) mp[p[i]]++;
vector<ll> d = {0}, w = {0}, pos = {0};
for (auto& [u, v] : mp) pos.push_back(u);
sort(pos.begin(), pos.end());
ll t = pos.size();
for (ll i = 1; i < t; i++) {
d.push_back(pos[i] - pos[i - 1]);
w.push_back(mp[pos[i]]);
}
pos.push_back(n);
d.push_back(n - pos.back());
w.push_back(0);
t++;
vector<vector<ll>> dp(t, vector<ll>(k, inf));
vector<vector<ll>> pd(t, vector<ll>(k, inf));
dp[0][0] = 0;
for (ll i = 1; i < t; i++) {
for (ll j = 0; j < k; j++) {
ll cst = (w[i] - j) / k;
dp[i][j] = dp[i - 1][mod(j - w[i], k)] + cst;
}
}
for (ll i = t - 2; i > 0; i--) {
for (ll j = 0; j < k; j++) {
ll cst = (w[i] - j) / k;
dp[i][j] = dp[i + 1][mod(j - w[i], k)] + cst;
}
}
ll res = inf;
for (ll i = 0; i < t - 1; i++) {
res = min(res, dp[i][0] + pd[i + 1][0]);
for (ll take = 1; take < k; take++) res = min(res, dp[i][take] + pd[i + 1][k - take] + l);
}
return res;
}
