#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
map < int , stack <int> > aparitii;
int suma[200001];
inline int Query (int indice)
{
int __suma = 0;
for ( ; indice ; indice ^= (indice & -indice))
{ __suma += suma[indice]; }
return __suma;
}
inline void Update (int indice , const int limita)
{
for ( ; indice <= limita ; indice += (indice & -indice))
{ suma[indice]++; }
}
long long count_swaps (vector <int> sir)
{
for (int indice = (int)sir.size() - 1 ; indice >= 0 ; indice--)
{ aparitii[sir[indice]].push(indice); }
vector <bool> numerotat(sir.size());
for (int indice = 0 , valoare = 0 ; indice < (int)sir.size() ; indice++) {
if (!numerotat[indice])
{
const int __indice = aparitii[-sir[indice]].top();
aparitii[-sir[indice]].pop();
aparitii[sir[indice]].pop();
if (sir[indice] > 0) { sir[__indice] = ++valoare; sir[indice] = ++valoare; }
else { sir[indice] = ++valoare; sir[__indice] = ++valoare; }
numerotat[__indice] = true;
numerotat[indice] = true;
}
}
long long necesar = 0;
for (int indice = (int)sir.size() - 1 ; indice >= 0 ; indice--)
{
necesar += Query(sir[indice] - 1);
Update(sir[indice] , (int)sir.size());
}
return necesar;
}
