#include "boxes.h"
#include <bits/stdc++.h>
long long delivery(int N, int K, int L, int p[])
{
long long ans;
K = std::min(K, N);
std::vector<long long> dist1, dist2;
dist1.push_back(0), dist2.push_back(0);
dist1.reserve(N / 2), dist2.reserve(N / 2);
for (int i = 0; i < N; ++i)
if (p[i] <= L / 2)
dist1.push_back(p[i]);
else
dist2.push_back(L - p[i]);
sort(dist1.begin(), dist1.end()), sort(dist2.begin(), dist2.end());
int a = (int)dist1.size(), b = (int)dist2.size();
std::vector<long long> pref1(a, 0), pref2(b, 0);
for (int i = 1; i < a; ++i)
pref1[i] = dist1[i] + ((i >= K) ? pref1[i - K] : 0);
for (int i = 1; i < b; ++i)
pref2[i] = dist2[i] + ((i >= K) ? pref2[i - K] : 0);
ans = 2 * (pref1[a - 1] + pref2[b - 1]);
for (int i = 1; i < K; ++i)
if (i >= a)
break;
else if (K - i >= b)
continue;
else
ans = std::min(ans, 2 * (pref1[a - i - 1]) + L + 2 * (pref2[b - (K - i) - 1]));
return ans;
}
/*
! Why L is added?
* Let say you have a ring with 3 Parts - each having size K
* Left K1 + Right K3 + Middle K2
* For 0 to K2, End Of K2 is much shorter to continue in same direction. That's why L.
*/
// * Efficient Solution
// long long delivery(int N, int K, int L, int p[])
// {
// long long ans;
// int it = std::lower_bound(p, p + N, (L + 1) / 2) - p;
// auto get_prf = [&](int i)
// {
// long long res = 0;
// for (; i >= 0; i -= K)
// res += 2 * p[i];
// return res;
// };
// auto get_suf = [&](int i)
// {
// long long res = 0;
// for (; i < N; i += K)
// res += 2 * (L - p[i]);
// return res;
// };
// ans = get_prf(it - 1) + get_suf(it);
// for (int i = std::max(0, it - K); i < it; i++)
// ans = std::min(ans, (long long)get_prf(i - 1) + L + get_suf(i + K));
// return ans;
// }
/*
Why L is added?
Let say you have a ring with 3 Parts - each having size K
Left K1 + Right K3 + Middle K2 (For This K2 End To 0 is much shorter to continue in same direction)
*/
