#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MAXN = 100000;
const int NIL = 0;
int v[2 * MAXN + 1], aib[2 * MAXN + 1], pr[2 * MAXN + 1], nextp[2 * MAXN + 1];
int n, n2;
void addBit(int poz) {
while (poz <= n2) {
aib[poz]++;
poz += (poz & (-poz));
}
}
int bitSum(int poz) {
int s;
s = 0;
while (poz > 0) {
s += aib[poz];
poz &= (poz - 1);
}
return s;
}
long long count_swaps(std::vector<int> s) {
int i, x, sum, p;
long long rez;
n2 = s.size();
n = n2 / 2;
for (i = 1; i <= n2; i++) {
v[i] = s[i - 1];
if (s[i - 1] < 0) {
v[i] = n - v[i];
}
}
for (i = n2; i > 0; i--) {
nextp[i] = pr[v[i]];
pr[v[i]] = i;
}
//perechile le pot determina de la inceput ca e a x-a poz din -a cu a x-a din a pt fiecare a si fiecare x ca sa fie cat mai apropiate
//e clar ca intre 2 din aceeasi pereche de la distanta x trebuie sa fac x sau x - 1 swapuri care sa le contina pe ele
//si swapurile care contin alte perechi nu conteaza
//deci pot la prima pe care o vad sa ii aduc perechea langa ea ca sa fac acele swapuri pe care le fac sigur si dupa celelalte sa fie mai apropiate intre ele
//deoareca inainte poate era a doua din prima pereche intre ele
rez = 0;
for (i = 1; i <= n2; i++) {
if (v[i] > 0) {
if (v[i] <= n) {
x = v[i] + n;
} else {
x = v[i] - n;
}
p = pr[x];
sum = p - i - bitSum(p - 1) + bitSum(i);
if (x <= n) {
sum--;//nu mai e nevoie de swapul dintre ele ca cel de st este in stanga celui de dr
}
rez += sum;
addBit(p);//nu mai e necesar si addBit(i)
pr[x] = nextp[pr[x]];
pr[v[i]] = nextp[pr[v[i]]];
v[p] = 0;
}
}
return rez;
}
