#include "wiring.h"
#include <bits/stdc++.h>
typedef long long ll;
#define ff first
#define ss second
using namespace std;
vector <pair <ll, int> > all;
const int BLUE = 0;
const int RED = 1;
const ll INF = 1e18;
ll dist(ll a, ll b) {
return abs(a - b);
}
const int N = 2e5 + 5;
vector <ll> pre(N), dp(N, INF);
ll sum(int a, int b) {
// cout << "SUM: " << a << ' ' << b << '\n';
return pre[a] - (b >= 0 ? pre[b] : 0);
}
long long min_total_length(vector<int> r, vector<int> b) {
int n = r.size() + b.size();
int color = RED;
if (b[0] < r[0]) color = BLUE;
all.push_back({-INF, 1-color});
color = RED;
if (b.back() > r.back()) color = BLUE;
all.push_back({INF, 1-color});
for (auto el : r) all.push_back({el, RED});
for (auto el : b) all.push_back({el, BLUE});
sort(all.begin(), all.end());
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + all[i].ff;
// cout << pre[i] << ' ';
}
// cout << "\n";
dp[0] = 0;
int pastSt = 1;
for (int i = 1; i <= n; i++) {
int j = i;
while(j + 1 <= n && all[j+1].ss == all[i].ss) j++;
for (int k = pastSt; k < i; k++) {
dp[k] = min(dp[k], dp[k-1] + dist(all[i].ff, all[k].ff));
}
int a, b;
for (a = i, b = i-1; a <= j && b >= pastSt; a++, b--) {
int k = a - i + 1;
ll curVal = (k * all[i].ff - sum(i-1, b-1)) + (sum(a, i-1) - k*all[i].ff);
dp[a] = min(dp[a], dp[b-1] + curVal);
}
for (int k = a; k <= j; k++) {
dp[k] = min(dp[k], dp[k-1] + dist(all[k].ff, all[i-1].ff));
}
pastSt = i;
i = j;
}
for (int k = 1; k <= n; k++) {
cout << dp[k] << ' ';
}
cout << '\n';
return dp[n];
}
