//#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll L;
int n,k;
ll A[10000007];
ll Distance(ll a,ll b)
{
ll d=(a>b)? a-b : b-a;
return (ll)min(d,L-d);
}
ll rangeSum(int s,int len)
{
int i=0;
int id;
ll total=0;
while(i<len){
id=(s+i)%n;
if(i==0)
total+=Distance(0,A[id]);
else
total+=Distance(A[(id+n-1)%n],A[id]);
i++;
}
i--;
id=(s+i)%n;
total+=Distance(0,A[id]);
return total;
}
ll interchange(int s,int len1,int len2) ///Swaps two ranges and return the difference compared to last configuration
{
ll diff=0;
if(len1==0 || len2==0) return 0;
int e=(s+len1-1+n)%n; //End of range
//Joins the two ranges in the actual split point
//by eliminating the distance to 0 and adding distance between e and e+1
diff-=Distance(0,A[e]);
diff-=Distance(0,A[(e+1)%n]);
diff+=Distance(A[e],A[(e+1)%n]);
//Splits the two ranges in the new split point
//by adding the distance to 0 and eliminating the distance between e and e+1
e=(s+len2-1+n)%n;
diff+=Distance(0,A[e]);
diff+=Distance(0,A[(e+1)%n]);
diff-=Distance(A[e],A[(e+1)%n]);
return diff;
}
ll Rotate(int s)
{
ll diff=0;
int id=s;
//For each start add the distance to its predecessor
if(n%k!=0)
diff+=Distance(A[(id-1+n)%n],A[id]);
for(int i=n%k;i<n;i+=k){
id=(i+s)%n;
diff+=Distance(A[(id-1+n)%n],A[id]);
}
//For each end subtract the distance to 0
id=(s+(n%k)-1)%n;
if(n%k!=0)
diff-=Distance(0,A[id]);
for(int i=n%k;i<n;i+=k){
id=(s+i+k-1)%n;
diff-=Distance(0,A[id]);
}
//For each new start add the distance to 0 and subtract the distance to its predecessor
id=(s+1)%n;
if(n%k!=0){
diff+=Distance(0,A[id]);
diff-=Distance(A[id],A[(id-1+n)%n]);
}
for(int i=n%k;i<n;i+=k){
id=(s+i+1)%n;
diff+=Distance(0,A[id]);
diff-=Distance(A[id],A[(id-1+n)%n]);
}
return diff;
}
ll answer[10000007];
long long delivery(int N, int K, int l, int p[]) {
L=l;
n=N;
k=K;
for(int i=0;i<n;i++){
A[i]=p[i];
}
if(n%k!=0) answer[0]+=rangeSum(0,n%k);
for(int i=n%k;i<n;i+=k){
answer[0]+=rangeSum(i,k);
}
ll minimum=answer[0];
for(int s=1;s<n;s++){ //s=start
if(s<k)
answer[s]=answer[s-1]+Rotate(s-1);
else{
answer[s]=answer[s-k]+interchange(s-k,n%k,k);
}
minimum=min(minimum,answer[s]);
}
//for(int i=0;i<n;i++){
// cout<<answer[i]<<" ";
//}
return minimum;
}
