#include "shoes.h"
#include <bitset>
#include <map>
#include <deque>
using namespace std;
template<class T>
struct BIT{
vector<T> bit;
explicit BIT(int N) : bit(N, 0) {}
void add(int pos, T val) {
for (++pos; pos < (int) bit.size(); pos += pos & -pos) {
bit[pos] += val;
}
}
T sum(int r) {
T res{};
for (++r; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
}
T sum(int l, int r) { return sum(r) - sum(l - 1); }
};
long long count_swaps(std::vector<int> s) {
int n = s.size();
BIT<int> bit(n + 1);
map<int, deque<int>> mp;
for (int i = 0; i < n; ++i) {
mp[s[i]].push_back(i);
}
using ll = long long;
ll ans = 0;
for (int i = 0; i < n; ++i) {
if (bit.sum(i, i)) continue;
int r = mp[-s[i]].front();
ans += r - i - bit.sum(i, r) - (s[i] < 0);
bit.add(r, 1);
mp[-s[i]].pop_front();
mp[s[i]].pop_front();
}
return ans;
}
