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