#include "shoes.h"
using namespace std;
#include <bits/stdc++.h>
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
map<lli, queue<lli> > mapa;
lli BIT[200002],visitados[200002],arr[200002];
lli n,ini,a,res,k,q;
void actualiza(lli pos, lli val){
while (pos <= 200000) {
BIT[pos] += val;
pos += pos&(-pos);
}
}
lli query(lli pos) {
lli res = 0;
while (pos > 0) {
res += BIT[pos];
pos -= pos&(-pos);
}
return res;
}
void limpia(lli a) {
while(visitados[mapa[a].front()] == 1) mapa[a].pop();
}
long long count_swaps(std::vector<int> s) {
n = s.size();
rep(i,1,n) {
arr[i] = s[i-1];
a = arr[i];
mapa[a].push(i);
}
ini=1;
res = 0;
rep (i,1,n) {
if (visitados[i] == 0) {
visitados[i] = 1;
actualiza(1,1);
actualiza(i,-1);
a = arr[i]*(-1);
if (arr[i] < 0) {
ini++;
limpia(a);
k = mapa[a].front();
mapa[a].pop();
visitados[k] = 1;
q = query(k)+k;
actualiza(1,1);
actualiza(k,-1);
res += q-ini;
ini++;
}
else {
limpia(a);
k = mapa[a].front();
mapa[a].pop();
visitados[k] = 1;
q = query(k)+k;
actualiza(1,1);
actualiza(k,-1);
res += q-ini;
ini+=2;
}
}
}
return res;
}
