#include "shoes.h"
#include <bits/stdc++.h>
using i64 = long long int;
struct BIT {
int n;
std::vector <int> a;
BIT(int _n = 0) : n(_n) {
a.assign(n, 0);
}
void update(int x, int v) {
for (; x < n; x |= x + 1)
a[x] += v;
}
int get(int x) const {
int ans = 0;
for (; x >= 0; x = (x & (x + 1)) - 1)
ans += a[x];
return ans;
}
};
i64 count_inversion(std::vector <int> a) {
i64 ans = 0;
int n = a.size();
BIT bit(n);
for (int i = 0; i < n; i += 1) {
ans += i - bit.get(a[i]);
bit.update(a[i], +1);
}
return ans;
}
i64 count_swaps(std::vector <int> a) {
int n = (int) a.size();
std::map <int, std::vector <int>> maps;
int T = 0;
std::vector <int> pos(n);
for (int i = 0; i < n; i += 1) {
int x = a[i];
if (maps[-x].empty()) {
maps[x].push_back(T);
pos[i] = T;
T += 2;
} else {
pos[i] = maps[-x].back() + (x > 0 ? +1 : -1);
maps[-x].pop_back();
}
}
return count_inversion(pos);
}
#ifdef ILOVELAMTER
int main(void) {
std::cout << count_swaps({-2, 2, 2, -2, -2, 2}) << '\n';
return 0;
}
#endif // ILOVELAMTER
