#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int TAILLEMAXI=100*1000+2,DECALAGE=(1<<17);
int dejavu[TAILLEMAXI];
ll rep,autre;
deque<int> parpointures[TAILLEMAXI][2];
int arbresomme[DECALAGE*2];
int somme(int deb,int fin){
if (deb==fin){
return arbresomme[deb];
}
if (deb%2==1){
return arbresomme[deb]+somme(deb+1,fin);
}
if (fin%2==0){
return arbresomme[fin]+somme(deb,fin-1);
}
return somme(deb/2,fin/2);
}
void remonter(int endroit){
if (endroit==0){
return ;
}
arbresomme[endroit]=arbresomme[endroit*2]+arbresomme[endroit*2+1];
remonter(endroit/2);
}
ll count_swaps(vector<int> chaussures) {
for (int i=0;i<(int)chaussures.size();i++){
if (chaussures[i]<0){
parpointures[-chaussures[i]][0].push_back(i);
}
else {
parpointures[chaussures[i]][1].push_back(i);
}
}
for (int i=0;i<(int)chaussures.size();i++){
if (dejavu[i]==0){
if (chaussures[i]>0){
autre=parpointures[chaussures[i]][0].front();
rep+=autre-i-somme(i+DECALAGE,autre+DECALAGE);
arbresomme[autre+DECALAGE]++;
remonter((autre+DECALAGE)/2);
dejavu[autre]=1;
}
else {
autre=parpointures[-chaussures[i]][1].front();
rep+=autre-i-1-somme(i+DECALAGE,autre+DECALAGE);
arbresomme[autre+DECALAGE]++;
remonter((autre+DECALAGE)/2);
dejavu[autre]=1;
}
parpointures[abs(chaussures[i])][0].pop_front();
parpointures[abs(chaussures[i])][1].pop_front();
}
}
return rep;
}
