#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int d[600000], m = 1;
void add(int l, int r){
l += m; r += m;
while(l < r){
if(l%2) d[l++ - 1]++; l /= 2;
if(r%2) d[--r - 1]++; r /= 2;
}
}
int sum(int x){
int s = 0; x += m;
while(x){
s += d[x-1]; x /= 2;
}
return s;
}
long long count_swaps(vector<int> a){
long long n = a.size(), r = 0, b[n]; set<int> p[n/2+1], q[n/2+1];
while(m < n) m *= 2;
for(int i = 0; i < n; i++){
if(a[i] < 0) p[-a[i]].insert(i); else q[a[i]].insert(i); b[i] = 0;
}
for(int i = 0; i < n; i++){
if(b[i]) continue; b[i] = 1;
if(a[i] > 0){
q[a[i]].erase(q[a[i]].begin());
int w = *p[a[i]].begin(); p[a[i]].erase(p[a[i]].begin());
r += w+sum(w)-sum(i)-i; add(i, w); b[w] = 1;
}
else{
p[-a[i]].erase(p[-a[i]].begin());
int w = *q[-a[i]].begin(); q[-a[i]].erase(q[-a[i]].begin());
r += w+sum(w)-sum(i)-i-1; add(i, w); b[w] = 1;
}
}
return r;
}
