#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
// _vector <int, 3> a(n, m, k);: int a[n][m][k].
// _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
template <typename T>
struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
}
const int MAX = 2e5 + 3;
const ll MOD[] = {1000000007, 998244353};
int n;
int last[2], cnt[MAX];
pair <int, int> x[MAX];
int cost[MAX];
ll dp[MAX];
ll prefix[MAX];
ll min_total_length(vector <int> a, vector <int> b) {
x[0] = {-1, -1};
for (int &i : a) x[++n] = make_pair(i, 0);
for (int &i : b) x[++n] = make_pair(i, 1);
sort(x + 1, x + n + 1);
last[0] = last[1] = -1e9;
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + x[i].first;
cost[i] = x[i].first - last[x[i].second ^ 1];
last[x[i].second] = x[i].first;
}
last[0] = last[1] = 2e9;
for (int i = n; i >= 1; i--) {
cost[i] = min(cost[i], last[x[i].second ^ 1] - x[i].first);
last[x[i].second] = x[i].first;
}
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + cost[i];
if (x[i].second == x[i - 1].second) cnt[i] = cnt[i - 1] + 1;
else cnt[i] = 1;
if (cnt[i] <= cnt[i - cnt[i]]) dp[i] = min(dp[i], dp[i - 2 * cnt[i]] + prefix[i] + prefix[i - 2 * cnt[i]] - 2 * prefix[i - cnt[i]]);
}
return dp[n];
}
