#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll=long long;
const ll MAX_PAIRES=100*1000+5,DECA=(1<<18);
ll nbPaires,rep;
vector<ll> listePos[MAX_PAIRES][2];
vector<pair<ll,ll>> listePaire;
ll cumu[2*DECA];
void ajout(ll pos) {
pos+=DECA;
cumu[pos]=1;
while (pos>1) {
pos/=2;
cumu[pos]=cumu[2*pos]+cumu[2*pos+1];
}
}
ll somme(ll deb,ll fin) {
if (deb==fin) {
return cumu[deb];
}
if (deb%2==1) {
return cumu[deb]+somme(deb+1,fin);
}
if (fin%2==0) {
return cumu[fin]+somme(deb,fin-1);
}
return somme(deb/2,fin/2);
}
ll count_swaps(vector<int> s) {
nbPaires=s.size()/2;
for (ll i=0;i<2*nbPaires;i++) {
if (s[i]>0) {
listePos[s[i]][0].push_back(i);
}
else {
listePos[-s[i]][1].push_back(i);
}
}
for (ll i=0;i<MAX_PAIRES;i++) {
for (ll j=0;j<(ll)listePos[i][0].size();j++) {
listePaire.push_back({listePos[i][0][j],listePos[i][1][j]});
}
}
sort(listePaire.begin(),listePaire.end(),[&](pair<ll,ll> a,pair<ll,ll> b) {
return min(a.first,a.second)<min(b.first,b.second);
});
for (auto nouv:listePaire) {
//cout<<nouv.first<<" "<<nouv.second<<endl;
if (nouv.first>nouv.second) {
rep--;
swap(nouv.first,nouv.second);
}
rep+=nouv.second-nouv.first-somme(DECA+nouv.first,DECA+nouv.second);
ajout(nouv.first);
ajout(nouv.second);
}
return rep;
}
