#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "boxes.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001001001
#define MOD 1000000007
struct MinQ{
stack<pair<ll,ll>>s1,s2;
int size(){
return (int)s1.size()+(int)s2.size();
}
void insert(ll x){
ll mn=x;
if (!s1.empty())
mn=min(mn,s1.top().second);
s1.push({x,mn});
}
void pop(){
assert((int)s1.size()+(int)s2.size()>0);
if (s2.size()==0){
while (s1.size()>0){
ll mn=s1.top().first;
if (!s2.empty())
mn=min(mn,s2.top().second);
s2.push({s1.top().first,mn});
s1.pop();
}
}
s2.pop();
}
ll query(){
assert((int)s1.size()+(int)s2.size()>0);
ll mn=INF;
if (s1.size()>0) mn=min(mn,s1.top().second);
if (s2.size()>0) mn=min(mn,s2.top().second);
return mn;
}
};
ll dpL[10000001],dpR[10000001];
ll delivery(int N, int K, int L, int pos[]){
MinQ q;
//from left side
q.insert(0);
for (int i=0;i<N;i++){
if (q.size()>K)
q.pop();
dpL[i]=q.query()+pos[i]+min(pos[i],L-pos[i]);
q.insert(dpL[i]);
}
while (q.size())
q.pop();
//from right side;
q.insert(0);
for (int i=N-1;i>=0;i--){
if (q.size()>K)
q.pop();
dpR[i]=q.query()+L-pos[i]+min(pos[i],L-pos[i]);
q.insert(dpR[i]);
}
ll ans=INF;
for (int i=0;i+1<N;i++){
if (i+1<N)
ans=min(ans,dpL[i]+dpR[i+1]);
}
ans=min(ans,dpL[N-1]);
ans=min(ans,dpR[0]);
return ans;
}
