#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 8e18;
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 computeR(vector<ll>&ldp, vector<ll>&rdp, int K, int posleft, int L, int pt_r){
int szlef = ldp.size() - 1, szrig = rdp.size() - 1;
ll rans = rdp[pt_r] * 2;
ll rema = (ll)(szlef-posleft + szrig-pt_r +K-1) / K * L;
rans = rans + rema;
return rans;
}
ll subAllPoints(int N, 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]);
}
ll answer = inf;
int pt_r = 0;
for (int i=0; i<ldp.size(); i++){
ll curans = ldp[i] * 2;
ll current = computeR(ldp,rdp,K,i,L,pt_r);
while(pt_r < (int)rdp.size()-1 && computeR(ldp,rdp,K,i,L,pt_r+1)<current){
current = computeR(ldp,rdp,K,i,L,pt_r+1);
pt_r++;
}
curans = curans + current;
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);
}
