#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
vector<long long> shoes, segTree;
vector<pair<int, int>> pairs;
unordered_map<long long, int> pos;
void update(int n, int l, int r, int x, int v) {
if (l == r) {
segTree[n] += v;
}
int m = (l+r) / 2;
if (x <= m) {
update(2*n, l, m, x, v);
} else {
update(2*n+1, m+1, r, x, v);
}
segTree[n] = segTree[2*n] + segTree[2*n+1];
}
int query(int n, int l, int r, int lb, int rb) {
if (rb < l or r <= lb) {
return 0;
}
if (l <= lb and rb <= r) {
return segTree[n];
}
int m = (l+r) / 2;
int s1 = query(2*n, l, m, lb, rb);
int s2 = query(2*n, m+1, r, lb, rb);
return s1 + s2;
}
long long count_swaps(vector<int> s) {
int n = s.size();
shoes = vector<long long>(n);
long long ans = 0;
for (int i = 0; i < n; i++) {
long long x = s[i];
shoes[i] = x;
if (pos.find(-x) != pos.end()) {
pairs.push_back({pos[-x], i});
pos.erase(-x);
ans += i - pos[-x] - 1;
if (x < 0) ans++;
}
else {
pos[x] = i;
}
}
sort(pairs.begin(), pairs.end());
segTree = vector<long long>(4*n);
for (pair<int, int> p: pairs) {
ans -= query(1, 0, n-1, p.first+1, p.second-1);
update(1, 0, n-1, p.first, -1);
update(1, 0, n-1, p.second, 1);
}
return ans;
}
