#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5+2;
int bit[mxN];
void add(int idx) {
for (; idx < mxN; idx |= (idx + 1)) bit[idx]++;
}
int sum(int idx) {
int sum = 0;
for (; idx >= 0; idx = ((idx) & (idx+1))-1) sum+=bit[idx];
return sum;
}
long long count_swaps(vector<int> s) {
long long ans = 0; const int n = s.size();
vector<bool> p(2*mxN, 0);
vector<int> pos[2*mxN], neg[2*mxN], ind(2*mxN, 0);
for (int i = 0; i < n; ++i) {
if (s[i] > 0) {
pos[s[i]].push_back(i);
}
else {
neg[-s[i]].push_back(i);
}
}
for (int i = 1; i <= n; ++i) {
sort(pos[i].begin(), pos[i].end());
sort(neg[i].begin(), neg[i].end());
}
int idx = 0;
while (idx < n) {
if (p[idx]) {
idx++;
continue;
}
// cout << idx << '\n';
// for (int i = 0; i < n; ++i) {
// cout << p[i] << '\n';
// }
// cout << "=n\n";
if (s[idx] < 0) {
ans += pos[-s[idx]][ind[-s[idx]]] - idx - 1 - (sum(pos[-s[idx]][ind[-s[idx]]]) - sum(idx));
// cout << pos[-s[idx]][ind[-s[idx]]] - idx - 1 - (sum(pos[-s[idx]][ind[-s[idx]]]) - sum(idx)) << ' ';
p[pos[-s[idx]][ind[-s[idx]]]] = 1;
add(pos[-s[idx]][ind[-s[idx]]]);
ind[-s[idx]]++;
}
else {
ans += neg[s[idx]][ind[s[idx]]] - idx - (sum(neg[s[idx]][ind[s[idx]]])-sum(idx));
// cout << neg[s[idx]][ind[s[idx]]] - idx - 1 - (sum(neg[s[idx]][ind[s[idx]]])-sum(idx)) << ' ';
p[neg[s[idx]][ind[s[idx]]]] = 1;
add(neg[s[idx]][ind[s[idx]]]);
ind[s[idx]]++;
}
idx++;
}
return ans;
}
