#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct segTree{
int *st;
int n;
segTree(int siz){
int x = ceil(log2(siz));
x++;
st=new int[(1<<x)];
fill(st,st+(1<<x),0);
n=siz-1;
for(int i = 0;i<siz;i++){
update(i,1);
}
}
void rupdate(int l, int r, int i, int val, int ind){
if(i<l||i>r){
return;
}
if(l==r){
st[ind]=val;
return;
}
int mid = (l+r)/2;
rupdate(l,mid,i,val,2*ind+1);
rupdate(mid+1,r,i,val,2*ind+2);
st[ind]=st[ind*2+1]+st[ind*2+2];
}
void update(int i, int val){
rupdate(0,n,i,val,0);
}
int rquery(int l, int r, int s, int e, int ind){
if(e<l||s>r){
return 0;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
return rquery(l,mid,s,e,ind*2+1)+rquery(mid+1,r,s,e,ind*2+2);
}
int query(int l, int r){
return rquery(0,n,l,r,0);
}
};
long long count_swaps(vector<int> s) {
long long ans = 0;
int n = s.size();
map<int,queue<int>>mp;
for(int i = 0;i<n;i++){
mp[s[i]].push(i);
}
segTree st(n);
for(int i = 0;i<n;i++){
if(st.query(i,i)==0)
continue;
int ind = mp[-s[i]].front();
mp[-s[i]].pop();
mp[s[i]].pop();
st.update(i,0);
if(s[i]<0){
ans+=st.query(i,ind)-1;
}
else{
ans+=st.query(i,ind);
}
st.update(ind,0);
}
return ans;
}
