#include <bits/stdc++.h>
#include "boxes.h"
/*
g++ -DEVAL -static -O2 -std=c++17 -o boxes -Wall -Wshadow -Wextra -Wconversion grader.cpp boxes.cpp
*/
using namespace std;
long long delivery(int N, int K, int L, int p[]) {
//cout <<N<<" "<<K<<" "<<L<<endl;
deque<int> dq;
for(int i=0;i<N;i++){
//cout<<p[i]<<" ";
dq.push_back(p[i]);
}//cout<<endl;
auto cost_right = [&](){
int ind = min(K,(int)dq.size())-1;
if(ind < 0 || ind >= (int)dq.size())return 0;
return dq[ind]+min(dq[ind],L-dq[ind]);
};
auto cost_left = [&](){
int cnt = 0;
while(dq.front() == 0)cnt++;
if(cnt > K)return 0;
int ind = min(K-cnt,(int)dq.size()-cnt);
if(ind < 0 || ind >= (int)dq.size())return 0;
return L-dq[(int)dq.size()-ind] + min(dq[(int)dq.size()-ind],L-dq[(int)dq.size()-ind]);
};
//cout << cost_right() <<"; \n"<<cost_left()<<endl;
long long res = 0;
int cnt = N;
while(cnt>0){
int R = cost_right();
int LL = cost_left();
if(R >= LL){
int x = K;
int dist = 0;
while(x-- && !dq.empty()){
dist = max(dist,dq.front()*2);
dq.pop_front();
}
res += R;
}else{
int x = K;
int dist = 0;
while(x-- && !dq.empty()){
if(dq.front() == 0){
dist = max(dist,dq.front()*2);
dq.pop_front();
}else {
dist = max(dist,(L-dq.back())*2);
dq.pop_back();
}
}
res += LL;
}
cnt-=K;
//cout<<res<<'\n';
}
return res;
}
/*
int main(){
int p[] = {1,2,5};
cout << delivery(3,2,8,p)<<'\n';
return 0;
}
*/
