#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct FenwichTree {
int n;
vector<int> f;
FenwichTree(int n): n(n), f(n + 1) {}
void Modify(int pos, int value) {
for (int i = pos + 1; i <= n; i += i & -i) {
f[i] += value;
}
}
int Get(int pos) {
int result = 0;
for (int i = pos + 1; i > 0; i -= i & -i) {
result += f[i];
}
return result;
}
};
vector<int> GetShoePairs(const vector<int>& s) {
int n = static_cast<int>(s.size());
vector<int> shoe_pair(n);
map<int, queue<int>> position;
for (int i = 0; i < n; ++i) {
int shoe = s[i];
if (!position[-shoe].empty()) {
int pos = position[-shoe].front();
shoe_pair[pos] = i;
shoe_pair[i] = pos;
position[-shoe].pop();
continue;
}
position[shoe].push(i);
}
return shoe_pair;
}
long long count_swaps(std::vector<int> s) {
int n = static_cast<int>(s.size());
vector<int> shoe_pair = GetShoePairs(s);
vector<int> used(n);
FenwichTree tree(n);
for (int i = 0; i < n; ++i)
tree.Modify(i, +1);
long long result = 0;
for (int i = 0; i < n; ++i) {
if (used[i])
continue;
int pr = shoe_pair[i];
int actual_pos = tree.Get(pr) - 1;
if (s[i] < 0)
result += actual_pos - 1;
else
result += actual_pos;
used[i] = used[pr] = 1;
tree.Modify(i, -1);
tree.Modify(pr, -1);
}
return result;
}
