#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define intt long long
struct segTree{
vector<intt> v;
intt size = 1;
void init(intt n){
while(size < n) size *= 2;
v.assign(2 * size, 0LL);
}
void set(int i, int j, int x, int lx, int rx){
if(rx - lx == 1){
v[x] = j;
return;
}
intt m = (lx + rx) / 2;
if(i < m) set(i, j, 2 * x + 1, lx, m);
else set(i, j, 2 * x + 2, m, rx);
v[x] = v[2 * x + 1] + v[2 * x + 2];
}
void set(int i, int j){
set(i, j, 0LL, 0LL, size);
}
intt sum(intt l, intt r, intt x, intt lx, intt rx){
if(lx >= l && rx <= r){
return v[x];
}
if(rx <= l || lx >= r) return 0;
intt m = (lx + rx) / 2;
intt s1 = sum(l, r, 2 * x + 1, lx, m);
intt s2 = sum(l, r, 2 * x + 2, m, rx);
return s1 + s2;
}
intt sum(int l, int r){
return sum(l, r, 0, 0, size);
}
};
long long count_swaps(vector<int> s) {
intt ans = 0;
segTree st;
st.init(s.size());
map<int, set<int>> siz;
for(int i = 0; i < s.size(); i++){
siz[s[i]].insert(i);
}
for(int i = 0; i < s.size(); i++){
if(s[i] == 0) continue;
int f = i;
siz[s[i]].erase(siz[s[i]].begin());
int sec = *siz[-s[i]].begin();
siz[-s[i]].erase(siz[-s[i]].begin());
ans += sec - f - 1 - st.sum(f, sec);
st.set(sec, 1);
s[sec] = 0;
if(s[f] > 0) ans += 1;
s[f]=0;
}
return ans;
}
