#include <bits/stdc++.h>
#ifdef DEBUGGING
#define debug(x) cout << (#x) << ": " << (x) << "\n";
#else
#define debug(x)
#endif
#include "boxes.h"
#define int long long
using namespace std;
void find_insert(int pos, set<array<int, 2>>& s)
{
auto it = s.lower_bound(array<int,2>({pos, -1}));
int val = 0;
if ((*it)[0] == pos)
{
val = (*it)[1];
s.erase(it);
}
s.insert({pos, val+1});
}
int get_sum(set<array<int, 2>>& s)
{
int sum = 0;
for (auto [pos, val] : s)
sum += val;
return sum;
}
int calculate_left(set<array<int, 2>>& left, int K)
{
debug("AA");
int cost = 0;
int pr = 0;
for (auto it = left.rbegin(); it != left.rend(); it++)
{
auto [pos, val] = *it;
if (val > pr)
{
val -= pr;
pr = 0;
int steps = val / K;
if ((val % K) != 0)
{
pr = K - (val % K);
steps++;
}
cost += steps * (pos * 2);
}
else
{
pr -= val;
}
}
debug("AB");
return cost;
}
int calculate_right(set<array<int,2>>& right, int K, int L)
{
debug("BA");
int cost = 0;
int pr = 0;
for (auto [pos, val] : right)
{
if (val > pr)
{
val -= pr;
pr = 0;
int steps = val / K;
if ((val % K) != 0)
{
steps++;
pr = K - (val % K);
}
cost += steps * (L - pos) * 2;
}
}
debug("BB");
return cost;
}
int calculate_steps(int a, int K)
{
int steps = a / K;
if ((a % K) != 0)
steps++;
return steps;
}
int delivery(int32_t N, int32_t K, int32_t L, int32_t p[])
{
debug("A");
set<array<int, 2>> left, right;
int mid = 0;
for (int i = 0; i < N; i++)
{
if (p[i] > L / 2)
find_insert(p[i], right);
else if (p[i] < L / 2)
find_insert(p[i], left);
else
mid++;
}
debug("B");
int left_sum = get_sum(left), right_sum = get_sum(right);
debug("E");
int left_leftover = left_sum % K, right_leftover = right_sum % K;
int llc = calculate_left(left, K), rlc = calculate_right(right, K, L);
int tmp = left_leftover;
debug("C");
assert(false);
for (auto it = left.rbegin(); it != left.rend() && tmp > 0;)
{
int dec = min((*it)[1], tmp);
tmp -= dec;
array<int, 2> new_value = *it;
new_value[1] -= dec;
it = decltype(it)(left.erase(next(it).base()));
if (new_value[1] > 0)
{
left.insert(new_value);
break;
}
}
debug("C");
tmp = right_leftover;
for (auto it = right.begin(); it != right.end() && tmp > 0;)
{
int dec = min((*it)[1], tmp);
tmp -= dec;
array<int, 2> new_value = *it;
new_value[1] -= dec;
it = right.erase(it);
if (new_value[1] > 0)
{
right.insert(new_value);
break;
}
}
debug("D");
int lwlc = calculate_left(left, K), rwlc = calculate_right(right, K, L);
int best = min({
llc + rlc + L * calculate_steps(mid, K),
lwlc + rlc + L * calculate_steps(mid + left_leftover, K),
llc + rwlc + L * calculate_steps(mid + right_leftover, K),
lwlc + rwlc + L * calculate_steps(mid + left_leftover + right_leftover, K)
});
return best;
}
