#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "boxes.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define int ll
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v;
int N, K, L;
int dist(int a, int b) {
if (a > b) swap(a, b);
return min(b - a, a + L - b);
}
long long delivery(signed n, signed k, signed l, signed p[]) {
N = n;
K = k;
L = l;
for (int i = 0; i < N; i++) v.pb(p[i]);
vector<int> ans={0};
vector<int> pref = {0};
for (int i = 1; i < N; i++) {
pref.pb(pref.back() + dist(v[i], v[i - 1]));
}
for (int i = 1; i <= N; i++) {
int tot = 0;
int j = i - 1;
tot += dist(0, v[j]);
tot += pref[j] - pref[max((int)0, j - K + 1)];
int o = v[0];
if (j - K + 1 >= 0) o = v[j - K + 1];
tot += dist(0, o);
if (j - K >= 0) {
tot += ans[j - K + 1];
}
ans.pb(tot);
}
// cout << endl;
reverse(v.begin(), v.end());
vector<int> ans1 = {0};
vector<int> pref1 = {0};
for (int i = 1; i < N; i++) {
pref1.pb(pref1.back() + dist(v[i], v[i - 1]));
}
for (int i = 1; i <= N; i++) {
int tot = 0;
int j = i - 1;
tot += dist(0, v[j]);
tot += pref1[j] - pref1[max((int)0, j - K + 1)];
int o = v[0];
if (j - K + 1 >= 0) o = v[j - K + 1];
tot += dist(0, o);
if (j - K >= 0) {
tot += ans1[j - K + 1];
}
ans1.pb(tot);
}
int mi = 1e18;
for (int i = 0; i <= N; i++) {
// cout << ans[i] << " " << ans1[N - i] << endl;
mi = min(mi, ans[i] + ans1[N - i]);
}
return mi;
}
