#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<int> f;
Fenwick(int _n) {
n = _n;
f.assign(n, 0);
}
void add(int pos, int val) {
for (int i = pos; i < n; i += i & -i) {
f[i] += val;
}
}
int get(int pos) {
int ans = 0;
for (int i = pos; i > 0; i -= i & -i) {
ans += f[i];
}
return ans;
}
};
long long count_inv(vector<int> ord) {
int len = ord.size();
Fenwick f(len + 1);
long long ans = 0;
for (auto vl : ord) {
ans += f.get(len) - f.get(vl);
f.add(vl, 1);
}
return ans;
}
long long count_swaps(vector<int> s) {
int n = s.size() / 2;
vector<int> ord_nw(n * 2);
int pos_l = 1;
vector<queue<int>> q_l(n + 1), q_r(n + 1);
for (int i = 0; i < n * 2; ++i) {
if (s[i] < 0) {
if (!q_r[-s[i]].empty()) {
ord_nw[i] = q_r[-s[i]].front();
q_r[-s[i]].pop();
} else {
ord_nw[i] = pos_l;
q_l[-s[i]].push(pos_l + 1);
pos_l += 2;
}
} else {
if (!q_l[s[i]].empty()) {
ord_nw[i] = q_l[s[i]].front();
q_l[s[i]].pop();
} else {
ord_nw[i] = pos_l + 1;
q_r[s[i]].push(pos_l);
pos_l += 2;
}
}
}
return count_inv(ord_nw);
}
