#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct segTree{
int n;
vector<long long> t;
segTree(int sz){
n = sz;
t.resize((n + 1) << 1, 0);
}
void sett(int i, int val){
t[i + n - 1] = val;
}
void build(){
for(int i = n - 1; i >= 1; i--){
t[i] = t[i << 1] + t[i << 1 | 1];
}
}
void update(int i, int val){
for(t[i += n - 1] = val; i > 1; i >>= 1){
t[i >> 1] = t[i] + t[i ^ 1];
}
}
long long query(int l, int r){
long long res = 0;
for(l += n - 1, r += n; l < r; l >>= 1, r >>= 1){
if(l & 1) res += t[l++];
if(r & 1) res += t[--r];
}
return res;
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size(), k = 0;
pair<int, int> a[n];
vector<int> used(n + 1, 0);
segTree st(n);
long long res = 0;
for(int i = 1; i <= n; i++){
if(!used[abs(s[i - 1])]){
used[abs(s[i - 1])] = i;
}
else{
k++;
a[k] = {used[abs(s[i - 1])], i};
}
st.sett(i, 1);
}
st.build();
for(int i = 1; i <= n / 2; i++){
res += st.query(a[i].first + 1, a[i].second - 1);
// if(s[a[i].second - 1] < 0) res++;
st.update(a[i].first, 0);
st.update(a[i].second, 0);
}
return res;
}
