#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n) : n(n), bit(n+1, 0) {}
void update(int i, int v) {
for (++i; i <= n; i += i & -i)
bit[i] += v;
}
int query(int i) {
int s = 0;
for (++i; i > 0; i -= i & -i)
s += bit[i];
return s;
}
int range(int l, int r) {
return query(r) - query(l-1);
}
};
long long count_swaps(vector<int> S) {
int n = S.size();
unordered_map<int, queue<int>> pos;
for (int i = 0; i < n; i++) {
pos[S[i]].push(i);
}
Fenwick fw(n);
for (int i = 0; i < n; i++) fw.update(i, 1);
ll ans = 0;
vector<bool> used(n, false);
for (int i = 0; i < n; i++) {
if (used[i]) continue;
int x = S[i];
pos[x].pop();
int j = pos[-x].front();
pos[-x].pop();
int swaps = fw.range(i, j) - 1;
ans += swaps;
if (x > 0) ans++;
fw.update(i, -1);
fw.update(j, -1);
used[i] = used[j] = true;
}
return ans;
}
