#include<bits/stdc++.h>
#include "shoes.h"
typedef long long ll;
using namespace std;
ll count_swaps(vector<int> vec){
ll n, r=0, s=0, a, t, x, k;
n = vec.size();
vector<queue<ll> > izq(n+1);
vector<queue<ll> > der(n+1);
vector<ll> prf(n+100, 0);
vector<pair<ll,ll> > pr;
for(int i=1;i<=n;i++){
t = abs(vec[i-1]);
if(vec[i-1] < 0){
if(der[t].empty())izq[t].push(i);
else {
x = der[t].front();
r+= i-x;
pr.push_back({x, i});
der[t].pop();
for(int k=x;k<=n;k+=(k&(-k)))prf[k]+=1;
for(int k=i;k<=n;k+=(k&(-k)))prf[k]+= (-1);
}
}
else {
if(izq[t].empty())der[t].push(i);
else {
x = izq[t].front();
r+= i-x-1;
pr.push_back({x, i});
izq[t].pop();
for(int k=x;k<=n;k+=(k&(-k)))prf[k]+=1;
for(int k=i;k<=n;k+=(k&(-k)))prf[k]+= (-1);
}
}
}
sort(pr.begin(), pr.end());
for(int i=0;i<pr.size();i++){
a=0;
for(int k=pr[i].second;k>=1;k-=(k&(-k)))a+=prf[k];
for(int k=pr[i].first;k<=n;k+=(k&(-k)))prf[k]+= (-1);
for(int k=pr[i].second;k<=n;k+=(k&(-k)))prf[k]+= 1;
s+=a;
}
return (r-s);
}
