#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
// 0 base index
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
// index,value
void update(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
// prefix sum till x
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
T get_range(int l, int r) {
return get(r) - (l > 0 ? get(l - 1) : 0);
}
};
long long count_swaps(std::vector<int> A) {
const int N = (int)A.size();
map<int, vector<int>> c_neg, c_pos;
for (int i = N - 1; i >= 0; i--)
if (A[i] < 0)
c_neg[A[i]].push_back(i);
else
c_pos[A[i]].push_back(i);
vector<bool> visited(N);
fenwick<int> add(N);
long long steps = 0;
int previous = 0;
for (int index = 0; index < N;) {
if (visited[index]) {
index++;
continue;
}
if ((index + add.get(index)) % 2 == 0) {
if (A[index] > 0) {
int it = c_neg[-A[index]].back();
c_neg[-A[index]].pop_back();
steps += (it + add.get(it)) - (index + add.get(index));
add.update(index, 1);
add.update(it, -1);
previous = abs(A[index]);
visited[it] = true;
index++;
} else {
c_neg[A[index]].pop_back();
previous = abs(A[index]);
index++;
}
}
else {
if (A[index] != previous) {
int it = c_pos[previous].back();
c_pos[previous].pop_back();
visited[it] = true;
steps += (it + add.get(it)) - (index + add.get(index));
add.update(index, 1);
add.update(it, -1);
} else {
c_pos[A[index]].pop_back();
index++;
}
}
}
return steps;
}
