#include "shoes.h"
#include <queue>
using namespace std;
int n;
int done[200005];
queue<int> occ[400005];
int t[400005];
int tmp[200005];
int qr(int l, int r){
int res = 0;
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1) res += t[l++];
if(r&1) res += t[--r];
}
return res;
}
void add(int pos){
for(t[pos+=n]++; pos>1; pos>>=1) t[pos>>1] = t[pos]+t[pos^1];
}
long long count_swaps(std::vector<int> s) {
n = (int)s.size();
for(int i=0; i<n; i++) occ[s[i]+n/2].push(i);
long long res = 0;
for(int i=0, pairs_done=0; i<n; i++){
if(done[i]) continue;
occ[s[i]+n/2].pop();
int pos = occ[-s[i]+n/2].front();
occ[-s[i]+n/2].pop();
res += pos-2*pairs_done+qr(pos, n);
if(s[i] < 0) res--;
add(pos);
done[pos]++;
pairs_done++;
}
return res;
}
