#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
deque<ll> dqx;
deque<ll> dqxv;
ll INF = 1e18;
void add(ll x, deque<ll> &dq){
while (dq.size()>0&&dq.front()>x){
dq.pop_front();
}
dq.push_front(x);
}
ll getMin(deque<ll> &dq){
return dq.back();
}
void remove(ll x, deque<ll> &dq){
if (dq.size()>0&&dq.back()==x){
dq.pop_back();
}
}
ll delivery(int n, int k, int l, int p[]) {
vector<ll> dp(n+1,INF);
dp[n]=0;
add(2*p[n-1]+dp[n],dqxv);
add(dp[n],dqx);
for (int i = n-1; i>=0; i--){
dp[i]=min(dp[i],getMin(dqxv));
dp[i]=min(dp[i],2*l-2*p[i]+getMin(dqx));
dp[i]=min(dp[i],l+getMin(dqx));
//cout<<i<<' '<<dp[i]<<'\n';
if (i==0){break;}
//remove
if (i+k-1<n){
remove(dp[i+k],dqx);
remove(2*p[i+k-1]+dp[i+k],dqxv);
}
//add
add(dp[i],dqx);
add(2*p[i-1]+dp[i],dqxv);
}
return dp[0];
}
