#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
using pr = pair<int, int>;
// const int INF = 1e9+7, MOD = 1e9+7;
const ll INF = 1e18;
vector<int> a;
int n, k, l;
struct dstack{
stack<ll> lnum, lmin, rnum, rmin;
void insert(ll x) {
rnum.push(x);
if (rmin.empty()) rmin.push(x);
else rmin.push(min(rmin.top(), x));
}
void erase() {
if (lnum.empty()) {
while (!rnum.empty()) {
ll num = rnum.top();
rnum.pop(); rmin.pop();
lnum.push(num);
if (lmin.empty()) lmin.push(num);
else lmin.push(min(lmin.top(), num));
}
}
lnum.pop();
lmin.pop();
}
ll value() {
ll res = INF;
if (!lmin.empty()) res = min(res, lmin.top());
if (!rmin.empty()) res = min(res, rmin.top());
return res;
}
};
vector<ll> deepee(const vector<int>& a, int s) {
vector<ll> dp(n+1, INF);
dp[0] = 0;
dstack cur;
cur.insert(0);
for (int i = 1; i <= n; i++) {
if (i > k) {
cur.erase();
}
// for (auto j : cur) cout << j.first << ' ';
// cout << '\n';
auto mn = cur.value();
int d = abs(a[i-1]-s) + min(a[i-1], l - a[i-1]);
dp[i] = mn + d;
cur.insert(dp[i]);
}
return dp;
}
long long delivery(int N, int K, int L, int p[]) {
n = N; k = K; l = L;
a.resize(n, 0);
for (int i = 0; i < n; i++) a[i] = p[i];
vector<ll> pref = deepee(a, 0);
reverse(a.begin(), a.end());
vector<ll> suff = deepee(a, l);
ll res = INF;
// res = min(pref[n], suff[n]);
for (int i = 0; i <= n; i++) {
res = min(res, pref[i] + suff[n-i]);
}
// cout << res;
return res;
}
