#include "boxes.h"
#include <bits/stdc++.h>
#define nmax 10000008
const long long inf = 1e18;
using namespace std;
long long n, k, l, pl, pr, pmid, a[nmax];
long long ans, f[nmax];
struct container{
long long cur, sz, sum[nmax];
void insert(long long x){
sz++;
cur--;
if (cur < 0)
cur += k;
sum[cur] += x;
}
void erase(long long x){
sum[cur] -= x;
cur++;
if (cur >= k)
cur -= k;
sz--;
}
long long cost(){
return sum[cur] * 2;
}
}u, v;
vector<long long>vtu, vtv;
long long calc(long long num){
return (num % k == 0) ? (num / k * l) : ((num / k + 1) * l);
}
long long delivery(int N, int K, int L, int p[]) {
ans = inf;
n = N;
k = K;
l = L;
if (l % 2 == 0)
pmid = l / 2;
else
pmid = -1;
f[n + 1] = 0;
for (long long i = n; i > 0; i--)
a[i] = p[i - 1];
a[0] = 0;
for (long long i = n; i >= 0; i--){
if (a[i] < l - a[i])
f[i] = inf;
else{
v.insert(l - a[i]);
f[i] = v.cost();
}
}
for (long long i = 0, j = 0; i <= n; i++){
if (i)
u.insert(a[i]);
if (a[i + 1] > l - a[i + 1]){
ans = min(ans, u.cost() + f[i + 1]);
break;
}
if (a[i] > l - a[i])
break;
while (j <= n && (a[j] < l - a[j] || a[j] * 2 < a[i] * 2 + l))
j++;
if (j > n)
ans = min(ans, u.cost() + calc(j - i - 1));
else{
long long r = j - i - 1;
if (r % k != 0)
r = k * (r / k + 0);
if (i + r >= n)
ans = min(ans, u.cost() + calc(n - i));
else{
ans = min(ans, u.cost() + calc(r) + f[i + r + 1]);
}
}
}
return ans;
}
