#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, va[200000];
vector<int> v;
pair<queue<int>, queue<int>> pa[100000];
ll eat(int l, int r) {
if (l + 1 == r) return 0;
int mi = (l + r) / 2, i = l, j = mi, k = l;
ll an = eat(l, mi) + eat(mi, r);
while (i < mi && j < r) {
if (v[i] < v[j]) {
va[k++] = v[i++];
} else {
va[k++] = v[j++];
an = an + mi - i;
}
}
while (i < mi) va[k++] = v[i++];
while (j < r) va[k++] = v[j++];
for (int ii = l; ii < r; ii++) v[ii] = va[ii];
return an;
}
ll count_swaps(std::vector<int> s) {
n = s.size();
for (int i = 0; i < n; i++) {
if (s[i] < 0) {
pa[-s[i]].first.push(i);
} else {
pa[s[i]].second.push(i);
}
}
for (int i = 0; i < n; i++) {
if (s[i] < 0) {
v.push_back(i);
v.push_back(pa[-s[i]].second.front());
s[pa[-s[i]].second.front()] = 0;
pa[-s[i]].first.pop();
pa[-s[i]].second.pop();
} else if (s[i] > 0) {
v.push_back(pa[s[i]].first.front());
v.push_back(i);
s[pa[s[i]].first.front()] = 0;
pa[s[i]].first.pop();
pa[s[i]].second.pop();
}
}
return eat(0, n);
}
