#include "boxes.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>
using namespace std;
template<typename T> void uin(T &a, T b) {
if (b < a) {
a = b;
}
}
const int N = 10 * 1000 * 1000 + 7; // for now
const long long INF = 1e18 + 228;
long long pref[N], suff[N];
priority_queue<long long> Q[N / 2];
long long mod[N / 2];
long long delivery(int n, int k, int L, int p[]) {
for (int i = 1; i <= n; ++i) {
pref[i] = 2LL * p[i - 1];
if (i > k) {
pref[i] += pref[i - k];
}
}
for (int i = n; i; --i) {
suff[i] = 2LL * (L - p[i - 1]);
if (i + k <= n) {
suff[i] += suff[i + k];
}
}
/*for (int i = 1; i <= n; ++i) {
cout << pref[i] << ' ';
}
cout << endl;
for (int i = 1; i <= n; ++i) {
cout << suff[i] << ' ';
}
cout << '\n';*/
long long answer = min(suff[1], pref[n]);
if (k < n / 2) {
int rem = 0;
for (int r = 1; r <= n + 1; ++r) {
mod[rem] += L;
Q[rem].push(-(pref[r - 1] - mod[rem]));
uin(answer, suff[r] + (-Q[rem].top() + mod[rem] ));
++rem;
if (rem == k) rem = 0;
}
} else {
for (int c = 0; c <= (n + k - 1) / k; ++c) {
long long cur = (long long)L * (long long)c;
long long addit = INF;
for (int l = 1; l <= n - c * k + 1; ++l) {
uin(addit, pref[l - 1] + suff[l + c * k]);
}
uin(answer, cur + addit);
}
}
return answer;
}
