#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct Fenwick{
int n;
vector<long long> bit;
Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int idx, long long val) {
idx++;
while (idx <= n) {
bit[idx] += val;
idx += idx & -idx;
}
}
long long sum(int idx) {
idx++;
long long res = 0;
while (idx > 0) {
res += bit[idx];
idx -= idx & -idx;
}
return res;
}
};
long long count_swaps(vector<int> s){
int m = (int)s.size();
map<int, vector<int> > pos;
map<int, vector<int> > neg;
for (int i = 0; i < m; i++) {
if (s[i] > 0){
pos[s[i]].push_back(i);
}
else{
neg[-s[i]].push_back(i);
}
}
vector<int> match(m, -1);
for(auto &it : pos){
int x = it.first;
for(int i = 0; i < (int)pos[x].size(); i++){
int a = pos[x][i];
int b = neg[x][i];
match[a] = b;
match[b] = a;
}
}
Fenwick fw(m);
for(int i = 0; i < m; i++){
fw.add(i, 1);
}
vector<bool> removed(m, false);
long long ans = 0;
for(int i = 0; i < m; i++){
if(removed[i]){
continue;
}
int idx = match[i];
long long cur_idx = fw.sum(idx) - fw.sum(i);
if(s[i] < 0){
ans += cur_idx - 1;
}
else{
ans += cur_idx;
}
removed[i] = true;
removed[idx] = true;
fw.add(i, -1);
fw.add(idx, -1);
}
return ans;
}
