#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> st;
void update(int pos, int node=1, int tl=0, int tr=n-1){
if (tl == tr){
st[node] = 1;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) update(pos, node*2, tl, tm);
else update(pos, node*2+1, tm+1, tr);
st[node] = st[node*2]+st[node*2+1];
}
int query(int l, int r, int node=1, int tl=0, int tr=n-1){
if (l <= tl && tr <= r) return st[node];
int res = 0;
int tm = (tl+tr)/2;
if (l <= tm) res += query(l, r, node*2, tl, tm);
if (tm+1 <= r) res += query(l, r, node*2+1, tm+1, tr);
return res;
}
ll count_swaps(vector<int> s){
n = s.size();
st.resize(4*n, 0);
vector<pair<int,int>> m;
unordered_map<int,queue<int>> um;
for (int i=0; i<n; i++) um[s[i]].push(i);
ll res = 0;
vector<bool> done(n, false);
for (int i=0; i<n; i++){
if (done[i]) continue;
um[s[i]].pop();
int tar = um[-s[i]].front();
um[-s[i]].pop();
res += tar-i-query(i, tar)-1;
if (s[i] > 0) res++;
update(tar);
done[tar] = true;
}
return res;
}
