#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> fen;
void update(int i, int v){
for(; i <= n; i+= i & -i) fen[i] += v;
}
int ans(int i){
if(i == 0) return 0;
int ns = 0;
for(; i >= 1; i -= i & -i) ns += fen[i];
return ns;
}
int query(int l, int r){
return ans(r) - ans(l-1);
}
long long count_swaps(std::vector<int> s) {
n = s.size();
fen.resize(n+1);
map<int, vector<int>> m;
long long ns = 0;
for(int i = s.size()-1; i >= 0; i--){
m[s[i]].push_back(i);
}
for(int i = 0; i < s.size(); i++){
if(query(i+1, i+1) == 1) continue;
if(s[i] < 0){
m[s[i]].pop_back();
int r = m[-s[i]].back();
int l = i+1;
m[-s[i]].pop_back();
int j = query(l+1, r+1);
ns += r-l - j;
update(r+1, 1);
}else{
m[s[i]].pop_back();
int r = m[-s[i]].back();
int l = i;
m[-s[i]].pop_back();
int j = query(l+1, r+1);
ns += r-l - j;
update(r+1, 1);
}
}
return ns;
}
