// ~ Be Name Khoda ~ //
#include "boxes.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 1e7 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int per[2][maxn5];
ll L, dp[2][maxn5], pos[maxn5];
ll dis(int ty, int id){
ll x = pos[id];
if(ty)
return x;
return L - x;
}
bool cmp0(int x, int y){
return mp(dis(0, x), x) < mp(dis(0, y), y);
}
bool cmp1(int x, int y){
return mp(dis(1, x), -x) < mp(dis(1, y), -y);
}
long long delivery(int n, int k, int l, int p[]) {
//cout << "here " << endl;
L = l;
for(int i = 0; i < n; i++)
pos[i] = p[i];
for(int i = 0; i < n; i++){
//cout << i << ' ' << pos[i] << ' ' << sum << endl;
per[0][i] = per[1][i] = i;
}
//return sum;
sort(per[0], per[0] + n, cmp0);
sort(per[1], per[1] + n, cmp1);
for(int tt = 0; tt < 2; tt++){
for(int i = 0; i < n; i++){
dp[tt][per[tt][i]] = (i >= k ? dp[tt][per[tt][i - k]] : 0) + 2 * dis(tt, per[tt][i]);
//cout << tt << ' ' << i << ' ' << dp[tt][per[tt][i]] << ' ' << per[tt][i] << endl;
}
}
ll sum = min(pos[per[1][n - 1]] * 2, (L - pos[per[1][0]]) * 2);
for(int i = 0; i < n - 1; i++)
sum = min(sum, pos[per[1][i]] * 2 + (L - pos[per[1][i + 1]]) * 2);
return sum;
ll ans = min(dp[1][per[1][n - 1]], dp[0][per[0][n - 1]]);
//cout << ans << ' ' << dp[1][per[1][n - 1]] << ' ' << dp[0][per[0][n - 1]] << ' ' << per[0][n - 1]<< endl;
for(int i = 0; i < n - 1; i++){
ans = min(ans, dp[0][per[0][i]] + dp[1][per[0][i + 1]]);
//cout << "ha? " << ans << ' ' << i << ' ' << dp[0][per[0][i]] << ' ' << dp[1][per[0][i + 1]] << ' ' << per[0][i] << ' ' << per[0][i + 1] << endl;
}
//cout << ans << endl;
return ans;
}
