#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
long long n , k , l , a [10000007] , b [10000007] , adp [10000007] , bdp [10000007];
long long dlta ( long long x , long long y )
{
if ( y == 0 || x == 0 ) return min ( abs ( x - y ) , l - abs ( x - y ) );
return abs ( x - y );
}
long long delivery(int N, int K, int L, int p[]) {
n = N , k = K , l = L;
for ( int i = 1 ; i <= n + 1 ; i ++ )
{
adp [i] = 1e18;
bdp [i] = 1e18;
if ( i != n + 1 )
{
a [i] = p [ i - 1 ];
b [i] = a [i];
}
}
long long ans = 1e18;
deque < pair < long long , int > > dq;
dq . push_back ( { 0 , 0 } );
for ( int i = 1 ; i <= n ; i ++ )
{
adp [i] = min ( adp [i] , dq [0] . first + 2 * a [i] );
while ( dq . size () )
{
long long x = ( * -- dq . end () ) . first;
if ( x >= adp [i] ) dq . pop_back ();
else break;
}
dq . push_back ( { adp [i] , i } );
if ( i - k >= dq [0] . second ) dq . pop_front ();
}
reverse ( a + 1 , a + n + 1 );
dq . clear ();
dq . push_back ( { 0 , 0 } );
for ( int i = 1 ; i <= n ; i ++ )
{
bdp [i] = min ( bdp [i] , dq [0] . first + 2 * ( l - a [i] ) );
while ( dq . size () )
{
long long x = ( * -- dq . end () ) . first;
if ( x >= bdp [i] ) dq . pop_back ();
else break;
}
dq . push_back ( { bdp [i] , i } );
if ( i - k >= dq [0] . second ) dq . pop_front ();
}
for ( int i = 0 ; i <= n ; i ++ )
{
long long ada = adp [i] - b [i] + dlta ( b [i] , 0 ) , adb = bdp [ n - i ] - ( l - a [ n - i ] ) + dlta ( a [ n - i ] , 0 );
adb = max ( adb , 0ll );
ans = min ( ans , ada + adb );
//cout << ' ' << i << ' ' << ada << ' ' << adb << endl;
}
return ans;
}
