#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> s) {
const int N = (int)s.size();
vector<int> closest_negative;
for (int i = N - 1; i >= 0; i--)
if (s[i] < 0) {
closest_negative.push_back(i);
}
map<int, vector<int>> closest_positive;
for (int i = N - 1; i >= 0; i--)
closest_positive[s[i]].push_back(i);
vector<bool> visited(N);
long long steps = 0;
int previous = -1;
fenwick<int> add(N);
for (int i = 0, index = 0; i < N; i++) {
if (visited[index]) {
index++;
continue;
}
if (i % 2 == 0) {
if (s[index] > 0) {
int it = closest_negative.back();
steps += (it + add.get(it)) - i;
previous = abs(s[it]);
visited[it] = true;
add.update(index, 1);
add.update(it, -1);
closest_negative.pop_back();
} else {
previous = abs(s[index]);
closest_negative.pop_back();
index++;
}
continue;
}
if (s[index] != previous) {
int it = closest_positive[previous].back();
steps += (it + add.get(it)) - i;
visited[it] = true;
add.update(index, 1);
add.update(it, -1);
closest_positive[previous].pop_back();
} else {
closest_positive[previous].pop_back();
index++;
}
}
return steps;
}
