// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#ifdef _DEBUG
long long min_total_length(std::vector<int> r, std::vector<int> b);
#else
#include "wiring.h"
#endif
ll inf = LLONG_MAX / 10;
template <typename T>
struct LzySegtree
{
vector<T> b;
vector<T> updates;
int n;
void prop(int l, int r, int i)
{
b[i] += updates[i];
if (l + 1 != r)
{
updates[i * 2 + 1] += updates[i];
updates[i * 2 + 2] += updates[i];
}
updates[i] = 0;
}
T segUpdate(int l, int r, int i, int ul, int ur, T delta)
{
prop(l, r, i);
if (ul >= r || ur <= l)
return b[i];
if (ul <= l && ur >= r)
{
updates[i] += delta;
prop(l, r, i);
return b[i];
}
int m = (l + r) / 2;
return b[i] = min(segUpdate(l, m, i * 2 + 1, ul, ur, delta), segUpdate(m, r, i * 2 + 2, ul, ur, delta));
}
T segGet(int l, int r, int i, int ql, int qr)
{
prop(l, r, i);
if (ql >= r || qr <= l)
return T(inf);
if (ql <= l && qr >= r)
return b[i];
int m = (l + r) / 2;
return min(segGet(l, m, i * 2 + 1, ql, qr), segGet(m, r, i * 2 + 2, ql, qr));
}
T segBuild(int l, int r, int i, vector<T> &a)
{
if (l + 1 == r)
return b[i] = a[l];
int m = (l + r) / 2;
return b[i] = min(segBuild(l, m, i * 2 + 1, a), segBuild(m, r, i * 2 + 2, a));
}
LzySegtree(vector<T> a)
{
n = a.size();
b.resize(4 * n, T(inf));
updates.resize(4 * n, 0);
segBuild(0, n, 0, a);
}
};
vector<pair<int, int>> all;
map<int, ll> mem;
/// @brief Assume r is sorted backwards and b forwards
/// @param r
/// @param b
ll match(vector<int> r, vector<int> b)
{
int n = r.size();
int m = b.size();
ll total = 0;
for (int i = 0; i < max(n, m); i++)
{
ll x = r.back();
ll y = b.back();
total += abs(x - y);
if (r.size() > 1)
r.pop_back();
if (b.size() > 1)
b.pop_back();
}
return total;
}
long long solve(int i)
{
if (mem.count(i))
return mem[i];
if (i == all.size())
return mem[i] = 0;
vector<int> r;
vector<int> b;
int index = i;
while (index < all.size() && all[index].second == all[i].second)
{
r.push_back(all[index].first);
index++;
}
reverse(r.begin(), r.end());
ll result = inf;
while (index < all.size() && all[index].second != all[i].second)
{
b.push_back(all[index].first);
ll cost = match(r, b);
result = min(result, cost + min(solve(index), solve(index + 1)));
index++;
}
return mem[i] = result;
}
long long min_total_length(std::vector<int> r, std::vector<int> b)
{
all.clear();
mem.clear();
int n = r.size();
int m = b.size();
for (int i : r)
all.push_back({i, -1});
for (int i : b)
all.push_back({i, 1});
sort(all.begin(), all.end());
vector<vector<int>> pockets;
pockets.push_back({all[0].first});
int index = all.size() - 1;
for (int i = 1; i < n + m; i++)
{
if (all[i].second != all[i - 1].second)
pockets.push_back({});
pockets.back().push_back(all[i].first);
}
vector<int> last_pocket;
vector<ll> last_scores;
ll last_skip = 0;
for (int i = pockets.size() - 1; i >= 0; i--)
{
int n = pockets[i].size();
vector<ll> scores(n, inf);
if (last_pocket.size() > 0)
{
vector<int> pocket = pockets[i];
vector<ll> last1 = last_scores;
vector<ll> last2 = last_scores;
last1.pop_back();
last2.erase(last2.begin());
assert(last1.size() == last_pocket.size());
ll additional = 0;
for (int i = 0; i < last_pocket.size(); i++)
{
additional += last_pocket[i] - pocket.back();
last1[i] += additional;
last2[i] += additional;
}
LzySegtree<ll> segte1(last1);
LzySegtree<ll> segte2(last2);
scores[pocket.size() - 1] = min(segte1.segGet(0, segte1.n, 0, 0, segte1.n), segte2.segGet(0, segte2.n, 0, 0, segte2.n));
// assert(scores[pocket.size() - 1] == solve(index));
int first_index = pocket.back();
pocket.pop_back();
index--;
int count = 1;
while (pocket.size())
{
int current = pocket.back();
count++;
segte1.segUpdate(0, segte1.n, 0, count - 1, segte1.n, first_index - current);
segte2.segUpdate(0, segte2.n, 0, count - 1, segte2.n, first_index - current);
segte1.segUpdate(0, segte1.n, 0, 0, count - 1, last_pocket[0] - current);
segte2.segUpdate(0, segte2.n, 0, 0, count - 1, last_pocket[0] - current);
scores[pocket.size() - 1] = min(segte1.segGet(0, segte1.n, 0, 0, segte1.n), segte2.segGet(0, segte2.n, 0, 0, segte2.n));
// assert(scores[pocket.size() - 1] == solve(index));
pocket.pop_back();
index--;
}
}
else
{
index -= pockets[i].size();
}
scores.push_back(last_skip);
if (last_pocket.size() > 0)
last_skip = scores[0];
else
last_skip = inf;
last_scores = scores;
last_pocket = pockets[i];
}
// assert(last_scores[0] == solve(0));
return last_scores[0];
}
#ifdef _DEBUG
int main()
{
int n, m;
int cnt;
cin >> cnt;
// assert(2 == scanf("%d %d", &n, &m));
// vector<int> r(n), b(m);
// for (int i = 0; i < n; i++)
// assert(1 == scanf("%d", &r[i]));
// for (int i = 0; i < m; i++)
// assert(1 == scanf("%d", &b[i]));
while (true)
{
vector<int> r, b;
for (int i = 0; i < cnt; i++)
{
if (rand() % 2)
{
b.push_back(i);
}
else
{
r.push_back(i);
}
}
assert(r.size() > 0);
assert(b.size() > 0);
long long res = min_total_length(r, b);
printf("%lld\n", res);
}
return 0;
}
#endif
