#include "shoes.h"

#include <algorithm>
#include <cassert>
#include <map>
#include <numeric>

long long count_swaps(std::vector<int> s) {
    int n = s.size() / 2;
    // if (n <= 8) {
    //     ;
    // }
    int64_t res = 0;
    // for (int i = 0, c = 0; i < 2 * n; i++) {
    //     if (s[i] < 0) {
    //         int c2 = i - c;
    //         res += abs(c - c2);
    //     } else {
    //         c++;
    //     }
    // }

    std::map<int, std::pair<std::vector<int>, std::vector<int>>> map;
    for (int i = 0; i < 2 * n; i++) {
        auto& pr = map[abs(s[i])];
        if (s[i] > 0) {
            pr.second.push_back(i);
        } else {
            pr.first.push_back(i);
        }
    }
    int64_t sum = 0;
    for (auto& [sz, pr] : map) {
        auto& [vc1, vc2] = pr;
        int m = vc1.size();
        for (int i = 0; i < m; i++) {
            int it = std::lower_bound(vc2.begin(), vc2.end(), vc1[i]) - vc2.begin();
            res += abs(i - it);

            sum += abs(vc1[i] - vc2[i]) - 1;
        }
    }

    // assert(sum % 2 == 0);
    // res += sum / 2;
    res += sum;

    return res;
}