#include "boxes.h"

#include <bits/stdc++.h>

long long delivery(int n, int k, int L, int p[]) {
    while (n && *p == 0) {
        n--;
        p++;
    }
    if (n == 0 || L == 1) {
        return 0;
    }
    k = std::min(k, n);

    int it = std::lower_bound(p, p + n, (L + 1) / 2) - p;
    assert(std::is_sorted(p, p + n));

    int left = it / k * k;
    int right = n - (n - it) / k * k;
    assert(left <= right);

    int64_t ans = 0;
    for (int i = 0; i < left; i += k) {
        ans += 2 * p[i + k - 1];
    }
    for (int i = n - 1; i >= right; i -= k) {
        ans += 2 * (L - p[i - k + 1]);
    }
    if (left == it || right == it) {
        if (left == it && right == it) {
            return ans;
        } else if (left == it) {
            ans += 2 * (L - p[it]);
        } else {
            ans += 2 * p[it - 1];
        }
        return ans;
    }
    int64_t min = 2 * L;
    if (right - left <= k) {
        min = std::min<int64_t>(min, L);
    }
    min = std::min<int64_t>(min, 2 * (p[it - 1] + L - p[it]));
    for (int i = left; i < right; i++) {
        if (i - left < k && i < it) {
            min = std::min<int64_t>(min, L + 2 * p[i]);
        }
        if (right - i <= k && i >= it) {
            min = std::min<int64_t>(min, L + 2 * (L - p[i]));
        }
    }
    // ans += 2 * (L - p[it]);
    // ans += 2 * p[it - 1];

    ans += min;

    // int64_t ans1 = 0;
    // for (int i = 0; i < it; i += k) {
    //     int nx = std::min(it - 1, i + k - 1);
    //     ans1 += 2 * p[nx];
    // }
    // for (int i = n - 1; i >= it; i -= k) {
    //     int nx = std::max(it, i - k + 1);
    //     ans1 += 2 * (L - p[nx]);
    // }
    // ans = std::min(ans, ans1);

    return ans;
}