#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
using namespace std;
struct Segtree {
int n;
vector<int> st;
Segtree(vector<int>& a) {
n = (int)a.size();
st = vector<int>(4*n);
build(1, 0, n-1, a);
}
void build(int p, int l, int r, const vector<int>& a) {
if (l == r) st[p] = a[l];
else {
int m = (l+r)/2;
build(2*p, l, m, a);
build(2*p+1, m+1, r, a);
st[p] = st[2*p]+st[2*p+1];
}
}
void change(int p, int l, int r, int i) {
if (l == r) st[p] = 1-st[p];
else {
int m = (l+r)/2;
if (i <= m) change(2*p, l, m, i);
else change(2*p+1, m+1, r, i);
st[p] = st[2*p]+st[2*p+1];
}
}
int sum(int p, int l, int r, int i, int j) {
if (i > j) return 0;
if (l == i && r == j) return st[p];
int m = (l+r)/2;
return sum(2*p, l, m, i, min(m, j))+sum(2*p+1, m+1, r, max(i, m+1), j);
}
void change(int i) { change(1, 0, n-1, i); }
int sum(int i, int j) { return sum(1, 0, n-1, i, j); }
};
ll count_swaps(vector<int> S) {
ll ans = 0;
int n = (int)S.size();
vector<int> pair(n);
vector<queue<int>> pos(n/2+1), neg(n/2+1);
for (int i = n-1; i >= 0; --i) {
if (S[i] > 0) {
if (neg[S[i]].empty()) {
pos[S[i]].push(i);
pair[i] = -1;
} else {
pair[i] = neg[S[i]].front();
neg[S[i]].pop();
}
} else {
if (pos[-S[i]].empty()) {
neg[-S[i]].push(i);
pair[i] = -1;
} else {
pair[i] = pos[-S[i]].front();
pos[-S[i]].pop();
}
}
}
vector<int> a(n, 1);
Segtree St(a);
for (int i = 0; i < n; ++i) {
if (pair[i] == -1) continue;
ans += St.sum(i+1, pair[i]-1);
if (S[i] > 0) ++ans;
St.change(i);
St.change(pair[i]);
}
return ans;
}
