#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<long long> fenw;
Fenwick(int n) : n(n), fenw(n+1, 0) {}
void update(int i, long long diff){
for(++i; i <= n; i += i & -i) fenw[i] += diff;
}
long long query(int i){
long long s = 0;
for(++i; i > 0; i -= i & -i) s += fenw[i];
return s;
}
// Query the sum in [l, r]
long long rangeQuery(int l, int r){
if(l > r) return 0;
return query(r) - query(l-1);
}
};
long long count_swaps(std::vector<int> s) {
int n = (int)s.size();
Fenwick fenw(n);
for(int i = 0; i < n; i++){
fenw.update(i, 1);
}
unordered_map<int, vector<int>> leftStack;
long long ans = 0;
for(int i = 0; i < n; i++){
int size = abs(s[i]);
if(s[i] < 0){
leftStack[size].push_back(i);
}
else {
int L = leftStack[size].back();
leftStack[size].pop_back();
int R = i;
int leftPos = min(L, R), rightPos = max(L, R);
long long between = fenw.rangeQuery(leftPos+1, rightPos-1);
ans += between;
fenw.update(L, -1);
}
}
return ans;
}
