#include "shoes.h"
#include <map>
#include <set>
using namespace std;
//#define int long long
struct FenwickTree {
vector<int> bit;
int n;
FenwickTree(int n) {
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
int sum(int r) {
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
long long count_swaps(vector<int> s) {
long long n = s.size();
vector<int> tmp(n, 1); FenwickTree in(tmp);
long long ans = 0; map<int, set<int>> sl, sr;
for (int i = 0; i < n; i++) {
if (s[i] < 0) {
sl[abs(s[i])].insert(i);
} else {
sr[abs(s[i])].insert(i);
}
}
for (int i = 0; i < n; i++) {
if (!in.sum(i, i)) continue;
int a = abs(s[i]);
if (s[i] < 0) {
// left shoe
auto nxt = sr[a].lower_bound(i);
int j = *nxt;
ans += (long long)in.sum(i + 1, j - 1);
in.add(i, -1); in.add(j, -1);
sr[a].erase(nxt);
continue;
}
// right shoe
auto nxt = sl[a].lower_bound(i);
int j = *nxt;
ans += (long long)in.sum(i + 1, j - 1) + 1;
in.add(i, -1); in.add(j, -1);
sl[a].erase(nxt);
}
return ans;
}
