#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();
set<int> closest_negative;
for (int i = N - 1; i >= 0; i--)
if (s[i] < 0) {
closest_negative.insert(i);
}
map<int, set<int>> closest_positive;
for (int i = N - 1; i >= 0; i--)
closest_positive[s[i]].insert(i);
vector<bool> visited(N);
int 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) {
auto it = closest_negative.begin();
steps += (*it + add.get(*it)) - i;
previous = abs(s[*it]);
visited[*it] = true;
add.update(index, 1);
add.update(*it, -1);
closest_negative.erase(it);
} else {
previous = abs(s[index]);
closest_negative.erase(index);
index++;
}
continue;
}
if (s[index] != previous) {
auto it = closest_positive[previous].begin();
steps += (*it + add.get(*it)) - i;
visited[*it] = true;
add.update(index, 1);
add.update(*it, -1);
closest_positive[previous].erase(it);
} else {
closest_positive[previous].erase(closest_positive[previous].begin());
index++;
}
}
return steps;
}
