#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T val) {
for (; x < n; x += x & -x) {
fenw[x] += val;
}
}
T get(int x) {
T ans{};
for (; x > 0; x -= x & -x) {
ans += fenw[x];
}
return ans;
}
};
long long count_swaps(vector<int> s) {
int n = (int) s.size() / 2, cur = 0;
vector<int> a(2 * n);
vector< queue<int> > q(2 * n + 1);
for (int i = 0; i < 2 * n; i++) {
if (q[n - s[i]].empty()) {
q[n + s[i]].push(i);
a[i] = 2 * cur;
cur++;
} else {
int j = q[n - s[i]].front();
q[n - s[i]].pop();
a[i] = a[j] + 1;
if (s[i] < 0) {
swap(a[i], a[j]);
}
}
}
fenwick<int> fenw(2 * n + 2);
long long ans = 0;
for (int i = 0; i < 2 * n; i++) {
ans += (long long) (i - fenw.get(a[i]));
fenw.modify(a[i] + 1, +1);
}
return ans;
}
