#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
template<typename T, int start>
class Fenwick {
private:
const T operation_neutral = 0;
T operation(T a, T b) { return a + b; }
T inverseOperation(T a, T b) { return a - b; }
public:
vector<T> fenwick;
int n;
Fenwick(int _n) {
n = _n;
fenwick.resize(n);
fill(fenwick.begin(), fenwick.end(), operation_neutral);
}
void update(int x, T v) {
for(int i = x + 1 - start; i <= n - start; i += (i & -i)) {
fenwick[i - 1 + start] = operation(fenwick[i - 1 + start], v);
}
}
T get(int x) {
T v = operation_neutral;
for(int i = x + 1 - start; i >= 1; i -= (i & -i)) {
v = operation(v, fenwick[i - 1 + start]);
}
return v;
}
T get(int l, int r) {
if(l == start) return get(r);
return inverseOperation(get(r), get(l-1));
}
};
long long count_swaps(vector<int> a) {
int n = a.size();
vector<int> left[n / 2 + 1], right[n / 2 + 1];
for(int i = 0; i < n; i++) {
if(a[i] < 0) left[-a[i]].push_back(i);
else right[a[i]].push_back(i);
}
int cnt[n / 2 + 1];
for(int i = 0; i <= n / 2; i++) cnt[i] = 0;
int pos[n];
int c = 0;
for(int i = 0; i < n; i++) {
if(a[i] < 0) {
pos[i] = c;
pos[right[-a[i]][cnt[-a[i]]]] = c + 1;
cnt[-a[i]]++;
c += 2;
}
}
Fenwick<int, 0> fw(n);
long long res = 0;
for(int i = 0; i < n; i++) {
res += fw.get(pos[i] + 1, n - 1);
fw.update(pos[i], 1);
}
return res;
}
