#include <algorithm>
#include "boxes.h"
using namespace std;
typedef long long llong;
const int maxN = 10000001;
int n;
llong dppref_[maxN], dpsuff_[maxN];
llong mn[maxN];
inline llong dppref(int i) { return (i < 0) ? 0 : dppref_[i]; }
inline llong dpsuff(int i) { return (i >= n) ? 0 : dpsuff_[i]; }
long long delivery(int n_, int k, int len, int pos[])
{
n = n_;
for (int i = 0; i < n; ++i)
dppref_[i] = 2LL * pos[i] + dppref(i - k);
for (int i = n - 1; i >= 0; --i)
dpsuff_[i] = 2LL * (len - pos[i]) + dpsuff(i + k);
llong ans = dpsuff(0);
const llong inf = 50000000000000000LL;
fill(mn, mn + maxN, inf);
for (int i = n - 1; i >= 0; --i)
{
ans = min(ans, dppref(i) + dpsuff(i + 1));
ans = min(ans, mn[i % k] + dppref(i - 1) - (i / k) * (llong)len);
++i;
mn[i % k] = min(mn[i % k], (i / k) * (llong)len + dpsuff(i));
--i;
}
/*for (int i = 0; i < n; ++i)
{
ans = min(ans, dppref(i) + dpsuff(i + 1));
for (int j = i + 2; j <= n; ++j)
{
if (i % k != j % k)
continue;
llong curans = j / k - i / k;
curans *= len;
curans += dppref(i - 1) + dpsuff(j);
ans = min(ans, curans);
}
}*/
return ans;
}
/*
3 2 8
1 2 5
10
*/
/*
3 2 100
10 47 60
120
*/
