#include "shoes.h"

#include <bits/stdc++.h>

using namespace std;

struct Fenwick {
    int n;
    vector<int> f;

    Fenwick(int _n) {
        n = _n;
        f.assign(n, 0);
    }

    void add(int pos, int val) {
        for (int i = pos; i < n; i += i & -i) {
            f[i] += val;
        }
    }

    int get(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= i & -i) {
            ans += f[i];
        }
        return ans;
    }
};

long long count_inv(vector<int> ord) {
    int len = ord.size();
    Fenwick f(len + 1);
    long long ans = 0;
    for (auto vl : ord) {
        ans += f.get(len) - f.get(vl);
        f.add(vl, 1);
    }
    return ans;
}

long long count_swaps(vector<int> s) {
    int n = s.size() / 2;
    vector<vector<pair<int, int>>> pos(n + 1);
    for (int i = 0; i < n * 2; ++i) {
        pos[abs(s[i])].emplace_back(i, s[i]);
    }
    long long ans = 0;
    for (int sz = 1; sz <= n; ++sz) {
        int pos_l = 1, pos_r = 2;
        vector<int> ord_nw;
        for (auto [p, vl] : pos[sz]) {
            if (vl < 0) {
                ord_nw.push_back(pos_l);
                pos_l += 2;
            } else {
                ord_nw.push_back(pos_r);
                pos_r += 2;
            }
        }
        ans += count_inv(ord_nw);
        for (int i = 0; i < (int)pos[sz].size(); ++i) {
            if (i % 2 == 0) {
                s[pos[sz][i].first] = -sz;
            } else {
                s[pos[sz][i].first] = sz;
            }
        }
    }
    vector<int> ord_nw;
    int pos_l = 1;
    map<int, int> pos_r;
    for (int i = 0; i < n * 2; ++i) {
        if (s[i] < 0) {
            ord_nw.push_back(pos_l);
            pos_r[-s[i]] = pos_l + 1;
            pos_l += 2;
        } else {
            ord_nw.push_back(pos_r[s[i]]);
        }
    }
    ans += count_inv(ord_nw);
    return ans;
}