#include "shoes.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;
long long s;
vector<ii> pos;
vector<ii> neg;
vector<ii> pairs;
int fen[200005]; ///pos of everything
void upd(int i,int j){
while (i<=200005){
fen[i]+=j;
i+=i&-i;
}
}
int query(int i){
int ans=0;
while (i){
ans+=fen[i];
i^=i&-i;
}
return ans;
}
long long count_swaps(std::vector<int> shoes) {
s=shoes.size();
for (int x=1;x<=s;x++){
fen[x]=1<<(__builtin_ctz(x));
if (shoes[x-1]<0) neg.push_back(ii(-shoes[x-1],x));
else pos.push_back(ii(shoes[x-1],x));
}
sort(pos.begin(),pos.end());
sort(neg.begin(),neg.end());
int a,b;
long long ans=0;
s>>=1;
for (int x=0;x<s;x++){
a=neg[x].second;
b=pos[x].second;
if (a>b) swap(a,b),ans++;
pairs.push_back(ii(a,b));
}
sort(pairs.begin(),pairs.end());
for (int x=0;x<s;x++){
a=pairs[x].first,b=pairs[x].second;
ans+=query(b)-query(a)-1;
upd(a,1);
upd(b,-1);
}
return ans;
}
