#include<bits/stdc++.h>
using namespace std;
const int MAXI = 100*1000 + 10;
queue<int> occ[2*MAXI];
bool dejaVu[MAXI];
const long long DECA = 1<<20;
int arbre[2*DECA];
void modif(int pos){
pos+=DECA;
arbre[pos] = 1;
while(pos>1){
pos/=2;
arbre[pos] = arbre[2*pos] + arbre[2*pos+1];
}
}
int calcSomme(int deb, int fin){
if(deb==fin)
return arbre[deb];
if(deb%2==1)
return arbre[deb] + calcSomme(deb+1, fin);
if(fin%2==0)
return calcSomme(deb, fin-1) + arbre[fin];
return calcSomme(deb/2, fin/2);
}
long long count_swaps(vector<signed> s) {
int nb = s.size();
for(int c=0; c<nb; c++){
occ[MAXI + s[c]].push(c);
}
long long res = 0;
for(int g=0; g<nb; g++){
if(!dejaVu[g]){
if(!occ[MAXI - s[g]].empty() && !occ[MAXI - s[g]].empty()){
int d = occ[MAXI - s[g]].front();
occ[MAXI - s[g]].pop();
occ[MAXI + s[g]].pop();
dejaVu[d] = true;
if(s[g] < 0){ // si chaussure gauche
res += d-g-1;
}
else{ // si chaussure droite
res+= d-g;
}
res -= calcSomme(g+DECA, d+DECA);
modif(d);
}
}
}
return res;
}
