#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll add = 0;

bool getArrays(vector<int> &X, vector<int> &P, vector<int> &A, vector<int> &B) {
    vector<int> a, b;
    int m = P.size();
    int prev = 0;
    int fpb = -1;
    for (int i = 0; i < m; i++) {
        for (int j = prev; j < P[i]; j++) {
            a.push_back(X[j]);
        }
        b.push_back(X[P[i]]);
        prev = P[i] + 1;
    }
    for (int i = prev; i < X.size(); i++) {
        a.push_back(X[i]);
    }
    
    int n = a.size();
    P.clear();
    int l = 0, r = m - 1;
    while (l < r) {
        if (b[l] == -b[r]) {
            l++;
            r--;
        } else if (abs(b[l]) > abs(b[r])) {
            P.push_back(b[l++]);
        } else if (abs(b[l]) <= abs(b[r])) {
            P.push_back(b[r--]);
        }
    }
    if (l == r) {
        if (b[l] != 0) {
            P.push_back(b[l]);
        }
    }
    sort(P.begin(), P.end());
    swap(b, P);

    m = b.size();
    if (m > n) {
        return 0;
    }

    for (int i = 0; i < m; i++) {
        if (b[i] >= 0 && fpb == -1) {
            fpb = i;
        }
    }
    if (fpb == -1) fpb = b.size();

    int lb = fpb, rb = b.size() - fpb;
    int each = (n + m) / 2;
    for (int i = 0; i < each - lb; i++) {
        if (a[i] > 0) {
            add += abs(a[i]);
            a[i] = 0;
        }
    }
    for (int i = n - 1; i >= n - (each - rb); i--) {
        if (a[i] < 0) {
            add += abs(a[i]);
            a[i] = 0;
        }
    }

    int lbound = each - lb;
    int rbound = n - (each - rb);
    X.clear();
    P.clear();
    for (int i = 0; i < lbound; i++) {
        X.push_back(abs(a[i]));
        assert(a[i] <= 0);
    } for (int i = rbound; i < n; i++) {
        P.push_back(a[i]);
        assert(a[i] >= 0);
    } for (int i = lbound; i < rbound; i++) {
        add += abs(a[i]);
    }
    for (int i = 0; i < m; i++) {
        (b[i] < 0 ? A : B).push_back(abs(b[i]));
    }

    reverse(A.begin(), A.end());
    reverse(X.begin(), X.end());
    return 1;
}

struct fenwick {
    int n;
    vector<ll> sum;
    fenwick(int N) {
        n = N;
        sum.assign(n + 1, 0);
    }

    void update(int i, int v) {
        i++;
        for (; i <= n; i += i & -i) 
            sum[i] += v;
    }

    ll query(int i) {
        ll ans = 0;
        for (; i; i -= i & -i) 
            ans += sum[i];
        return ans;
    }

    ll get(int l, int r) {
        return query(r + 1) - query(l);
    }
};

long long get_cost(vector<int> a, vector<int> b) {
    vector<int> A, B;
    if (!getArrays(a, b, A, B)) {
        return -1;
    }
    assert(a.size() - B.size() == b.size() - A.size());
    int off = a.size() - B.size();
    
    int n = a.size(), N = A.size();
    int m = b.size(), M = B.size();
    int tot = n + N;
    
    fenwick sgA(A.size() + 1), sgB(B.size() + 1), sga(a.size() + 1), sgb(b.size() + 1);
    vector<vector<int>> chA(off + 1), chB(off + 1), cha(off + 1), chb(off + 1);
    for (int i = 0; i < A.size(); i++) {
        sgA.update(i, A[i]);
        int id = lower_bound(b.begin(), b.end(), A[i]) - b.begin();
        int get = max(0, id - i);
        if (get <= off) {
            chA[get].push_back(i);
        }
    } for (int i = 0; i < B.size(); i++) {
        sgB.update(i, B[i]);
        int id = lower_bound(a.begin(), a.end(), B[i]) - a.begin();
        int get = max(0, id - i);
        if (get <= off) {
            chB[get].push_back(i);
        }
    } for (int i = 0; i < a.size(); i++) {
        sga.update(i, -a[i]);
        int id = upper_bound(B.begin(), B.end(), a[i]) - B.begin() - 1;
        int get = max(0, i - id);
        if (get <= off) {
            cha[get].push_back(i);
        }
    } for (int i = 0; i < b.size(); i++) {
        sgb.update(i, -b[i]);
        int id = upper_bound(A.begin(), A.end(), b[i]) - A.begin() - 1;
        int get = max(0, i - id);
        if (get <= off) {
            chb[get].push_back(i);
        }
    }

    vector<array<int, 2>> Am(tot + 1), Bm(tot + 1);
    Am[0] = Bm[0] = {-1, -1};
    for (int i = 0; i < m; i++) 
        Bm[i + 1] = {b[i], i};
    for (int i = 0; i < M; i++) 
        Bm[i + m + 1] = {B[i], i + m};
    for (int i = 0; i < n; i++) 
        Am[i + 1] = {a[i], i};
    for (int i = 0; i < N; i++) 
        Am[i + n + 1] = {A[i], i + n};
    sort(Am.begin(), Am.end());
    sort(Bm.begin(), Bm.end());

    vector<vector<int>> places(off + 1), getNxt(off + 1);
    places[off].push_back(0);
    vector<array<int, 4>> counts(tot + 1); // {a, A, b, B}
    vector<int> need(tot + 1);
    need[0] = off;
    for (int i = 1; i <= tot; i++) {
        counts[i] = counts[i - 1];
        need[i] = need[i - 1];

        bool s = Am[i][1] >= n;
        bool k = Bm[i][1] >= m;
        counts[i][s]++;
        counts[i][k + 2]++;
        
        bool ok = false;
        if (s == k) {
            if (s) {
                need[i]++;
            } else if (!s) {
                need[i]--;
                ok = true;
            }
        }
        if (need[i] <= off && need[i] >= 0) {
            if (ok) getNxt[need[i]].push_back(i);
            places[need[i]].push_back(i);
        }
    }

    assert(need[tot] == 0);

    vector<ll> dp(tot + 1, 1e18);
    auto getCost = [&](array<int, 4> &x, array<int, 4> &y) { // {a, A, b, B}
        ll ret = 0;
        if (x[0] != y[0]) 
            ret += sga.get(x[0], y[0] - 1) + sgB.get(x[3], y[3] - 1);
        if (x[2] != y[2]) 
            ret += sgA.get(x[1], y[1] - 1) + sgb.get(x[2], y[2] - 1);
        return ret;
    };
    dp[0] = 0;
    int cnt = 0;
    for (int i = off; i >= 0; i--) {
        for (int &x : chA[cnt]) {
            sgA.update(x, -2 * A[x]);
        } for (int &x : chB[cnt]) {
            sgB.update(x, -2 * B[x]);
        } for (int &x : cha[cnt]) {
            sga.update(x, 2 * a[x]);
        } for (int &x : chb[cnt]) {
            sgb.update(x, 2 * b[x]);
        }
        for (int j = 0; j < places[i].size(); j++) {
            int x = places[i][j];
            
            if (j + 1 != places[i].size()) {
                int nxt = places[i][j + 1];
                dp[nxt] = min(dp[nxt], dp[x] + getCost(counts[x], counts[nxt]));
            }
            if (i) {
                int id = upper_bound(getNxt[i - 1].begin(), getNxt[i - 1].end(), x) - getNxt[i - 1].begin();
                if (id != getNxt[i - 1].size()) {
                    int nxt = getNxt[i - 1][id];
                    dp[nxt] = min(dp[nxt], dp[x] + getCost(counts[x], counts[nxt - 1]) + 
                    abs(Am[nxt][0] - Bm[nxt][0]));
                } 
            }
        }
        cnt++;
    }

    return add + dp[tot];
}