#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int seg[N << 1];
void upd (int nd, int l, int r, int p) {
if (l == r) {
seg[nd] ^= 1;
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p);
} else {
upd(rs, mid + 1, r, p);
}
seg[nd] = seg[nd + 1] + seg[rs];
}
void upd (int p) {
return upd(0, 0, N - 1, p);
}
int qry (int nd, int l, int r, int s, int e) {
if (l >= s && r <= e) {
return seg[nd];
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
return qry(nd + 1, l, mid, s, e);
} else {
if (mid < s) {
return qry(rs, mid + 1, r, s, e);
} else {
return qry(nd + 1, l, mid, s, e) + qry(rs, mid + 1, r, s, e);
}
}
}
int qry (int l, int r) {
return qry(0, 0, N - 1, l, r);
}
long long count_swaps(std::vector<int> s) {
int n = (int) s.size();
vector<queue<int>> v[2];
v[0].resize(n);
v[1].resize(n);
long long ans = 0;
for (int i = 0; i < n; ++i) {
bool neg = s[i] < 0;
if (neg) s[i] = -s[i];
s[i]--;
if (neg) {
if (v[0][s[i]].size()) {
int match = v[0][s[i]].front();
upd(match);
ans += i - match - qry(match + 1, i);
v[0][s[i]].pop();
} else {
upd(i);
v[1][s[i]].push(i);
}
} else {
if (v[1][s[i]].size()) {
int match = v[1][s[i]].front();
upd(match);
ans += i - match - 1 - qry(match + 1, i);
v[1][s[i]].pop();
} else {
upd(i);
v[0][s[i]].push(i);
}
}
}
return ans;
}
