#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
struct _ {
int n = 0;
vector<int> nums, st;
void build(int i, int L, int R) {
if (L == R) {
st[i] = 1;
return;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
build(x, L, m);
build(y, m + 1, R);
st[i] = st[x] + st[y];
}
int query(int i, int L, int R, int l, int r) {
if (l > r) return 0;
if (L == l && r == R) {
return st[i];
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (r <= m) {
return query(x, L, m, l, r);
} else if (l > m) {
return query(y, m + 1, R, l, r);
} else {
int q1 = query(x, L, m, l, m);
int q2 = query(y, m + 1, R, m + 1, r);
return q1 + q2;
}
}
void update(int i, int L, int R, int p) {
if (L == R) {
st[i] = 0;
return;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (p <= m) {
update(x, L, m, p);
} else {
update(y, m + 1, R, p);
}
st[i] = st[x] + st[y];
}
void update(int p) {
update(0, 0, n - 1, p);
}
int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
void build(vector<int> &s) {
n = s.size() + 1;
nums = s;
st.resize(4 * n);
build(0, 0, n - 1);
}
} tree;
int find(int x) {
if (x < 0)
return abs(x) * 2 - 1;
else
return abs(x) * 2;
}
ll count_swaps(vector<int> s) {
int n = s.size() / 2;
int m = s.size();
int sz = 0;
for (int i = 0; i < m; ++i) {
int x = find(s[i]);
sz = max(sz, x);
}
vector<queue<int>> pos(sz + 1);
for (int i = 0; i < m; ++i) {
int x = find(s[i]);
pos[x].push(i);
}
tree.build(s);
int res = 0;
for (int l = 0; l < m; ++l) {
int x = find(-s[l]);
int r = pos[x].front();
pos[x].pop();
if (s[l] > s[r]) {
res += tree.query(l, r - 1);
tree.update(l);
} else {
res += tree.query(l + 1, r - 1);
tree.update(l + 1);
}
tree.update(r - 1);
}
return res;
}
// int main() {
// cin.tie(0)->sync_with_stdio(0);
// vector<vector<int>> tc{
// {2, -1, 3, -4, -2, 4, -3, 1}};
// for (auto &v : tc) {
// cout << count_swaps(v) << '\n';
// }
// }
