#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 8e18;
const int NAX = 10000005;
vector<ll> dp(NAX, inf);
int maxRight = 0;
ll subtwo(int N, int K, int L, int p[]){
ll answer = 0;
if (L==1) return answer;
int mxd = L/2;
int cnt = 0, cntright = 0;
for (int i=0; i<N; i++){
if (p[i] <= mxd) cnt++;
if ((p[i] == 0 || p[i] >= mxd+1) && N%2==1) cntright++;
else if ((p[i] == 0 || p[i] >= mxd) && N%2==0) cntright++;
}
if (cnt == N) return 2LL*p[N-1];
if (cntright == N) return 2LL*(L-p[0]);
answer = L;
ll maxleft, maxright;
maxleft = maxright = 0;
for (int i=0; i<N; i++){
if (p[i] <= mxd){
maxleft = max(maxleft,(ll)p[i]);
}else{
maxright = max(maxright, (ll)L-p[i]);
}
}
ll answer2 = maxleft*2LL + maxright*2LL;
answer = min(answer, answer2);
return answer;
}
ll subone(int N, int K, int L, int p[]){
ll answer = 0;
for (int i=0; i<N; i++){
answer = answer + min(p[i],L-p[i])*2;
}
return answer;
}
ll subAllPoints(int N, const int K, int L, int p[]){
vector<int> ar;
for (int i=0; i<N; i++){
ar.push_back(p[i]);
}
reverse(ar.begin(), ar.end());
while(ar.size() && ar.back() == 0) ar.pop_back();
reverse(ar.begin(), ar.end());
if (ar.empty()) return 0;
vector<int> le,ri;
int mxd = L/2;
for (int i=0; i<ar.size(); i++){
if (ar[i] <= mxd) le.push_back(ar[i]);
else ri.push_back(ar[i]);
}
//
reverse(ri.begin(), ri.end());
vector<ll> ldp,rdp;
ldp.push_back(0);
rdp.push_back(0);
for (int i=0; i<le.size(); i++){
ldp.push_back(-1);
int cpos = i+1;
int lpos = max(1,cpos-K+1);
ldp[cpos] = ldp[lpos-1] + le[i];
}
for (int i=0; i<ri.size(); i++){
rdp.push_back(-1);
int cpos = i+1;
int lpos = max(1,cpos-K+1);
rdp[cpos] = rdp[lpos-1] + (L - ri[i]);
}
//compte dp: (go in reverse of array dp right)
for (int i=(int)rdp.size()-1, helpermxR=0; i>=0; i--,helpermxR++){
int sz = (int)rdp.size()-1 - i;
ll newbest = (ll)sz / K * L + rdp[i]*2;
dp[helpermxR%K] = min(dp[helpermxR%K], newbest);
maxRight = max(maxRight,helpermxR%K);
}
// compute the final answer:
ll answer = inf;
for (int i=0; i<ldp.size(); i++){
ll curans = ldp[i] * 2;
int sz = (int)ldp.size()-1 - i;
ll remaleft = (ll)((ll)sz + K-1) / K * L;
curans = curans + remaleft;
int complement = 0;
if (sz%K) complement = K - sz%K;
complement = min(complement, maxRight);
ll curansRight = dp[complement];
curans = curans + curansRight;
answer = min(answer, curans);
}
return answer;
}
ll delivery(int N, int K, int L, int p[]) {
if (K==1) return subone(N,K,L,p);
else if (K==N) return subtwo(N,K,L,p);
else return subAllPoints(N,K,L,p);
}
