#include "shoes.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
long long count_swaps(vector<int> A) {
int n = (int)A.size();
vector<queue<int>> positives(n+1);
vector<queue<int>> negatives(n+1);
vector<int> partner(n);
for(int i = 0; i < n; ++i) {
auto &positions = A[i] < 0 ? positives[-A[i]] : negatives[A[i]];
if(positions.empty()) {
if(A[i] > 0) {
positives[A[i]].push(i);
} else {
negatives[-A[i]].push(i);
}
} else {
partner[i] = positions.front();
partner[positions.front()] = i;
positions.pop();
}
}
vector<int> fenwick(n+1);
auto sum = [&](int id) -> int {
int answer = 0;
for(++id; id > 0; id -= id & -id) {
answer += fenwick[id];
}
return answer;
};
auto update = [&](int id, int v) {
for(; id <= n; id += id & -id) {
fenwick[id] += v;
}
};
auto add = [&](int l, int r, int v) {
++l, ++r;
update(l, v);
update(r+1, -v);
};
vector<bool> processed(n, false);
long long answer = 0;
for(int i = 0; i < n; ++i) {
if(!processed[i]) {
int j = partner[i];
processed[i] = processed[j] = true;
int real_i = sum(i) + i;
int real_j = sum(j) + j;
answer += real_j - real_i - (A[j] > 0);
add(i, j, 1);
}
}
return answer;
}
