#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const long long BIG = 1000000000000000000LL;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
int nbTeams, maxCarry, nbPos;
const int borne = (int)(1e7) + 5;
ll dp[borne][2];
int hd[borne][2];
int pos[borne];
void comp(int gt, int base)
{
dp[0][gt] = 0;
int deliv = base;
if (deliv == 0) deliv = maxCarry;
dp[deliv][gt] = hd[deliv-1][gt];
deliv += maxCarry;
while (deliv <= nbTeams) {
int prev = deliv-maxCarry;
dp[deliv][gt] = dp[prev][gt];
dp[deliv][gt] += 2*hd[prev-1][gt];
dp[deliv][gt] += hd[deliv-1][gt];
dp[deliv][gt] -= hd[prev-1][gt];
deliv += maxCarry;
}
}
long long delivery(int N, int K, int L, int p[])
{
nbTeams = N;
maxCarry = K;
nbPos = L;
form(i, nbTeams) pos[i] = p[i];
hd[0][0] = pos[0];
form2(i, 1, nbTeams) {
hd[i][0] = hd[i-1][0] + (pos[i] - pos[i-1]);
}
hd[0][1] = nbPos - pos[N-1];
form2(i, 1, nbTeams) {
int nextPos = N-i-1;
int prevPos = N-i;
hd[i][1] = hd[i-1][1] + (pos[prevPos] - pos[nextPos]);
}
form(base, maxCarry) {
comp(0, base);
comp(1, base);
}
form(gt, 2) form2(i, 1, nbTeams+1) dp[i][gt] += min(hd[i-1][gt], nbPos-hd[i-1][gt]);
ll rep = BIG;
form(g, nbTeams+1) {
int rst = nbTeams-g;
chmin(rep, dp[g][0] + dp[rst][1]);
}
return rep;
}
