#include "shoes.h"
#include <algorithm>
#include <iostream>
using namespace std;
class FenwickTree {
private:
int sz;
vector <int> v;
int lsb(int x) {
return (x & (-x));
}
public:
FenwickTree(int n) {
sz = n;
v.resize(sz + 1);
}
void update(int poz) {
for (int i = poz; i <= sz; i += lsb(i)) {
v[i]++;
}
}
int query(int poz) {
int ans = 0;
for (int i = poz; i; i -= lsb(i)) {
ans += v[i];
}
return ans;
}
};
int n;
long long computeInversions(vector <int> v) {
long long inv = 0;
FenwickTree aib(2 * n);
for (int i = 2 * n - 1; i >= 0; i--) {
inv += aib.query(v[i]);
aib.update(v[i] + 1);
}
return inv;
}
long long count_swaps(vector<int> s) {
n = (int) s.size() / 2;
vector <int> v(2 * n), ord;
vector <vector <int>> pos(n + 1, vector <int>());
int p1 = 0;
for (int i = 0; i < 2 * n; i++) {
if (s[i] < 0) {
v[i] = p1;
p1 += 2;
ord.push_back(-s[i]);
}
}
for (int i = 2 * n - 1; i >= 0; i--) {
if (s[i] > 0) {
int x = s[i];
pos[x].push_back(i);
}
}
for (int i = 0; i < n; i++) {
int x = ord[i];
int poz = pos[x].back();
pos[x].pop_back();
v[poz] = 2 * i + 1;
}
return computeInversions(v);
}
