#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
int t[4 * mxN];
void update(int x, int lx, int rx, int i, int v) {
if (lx == rx) {
t[x] = v;
return;
}
int mx = (lx + rx) >> 1;
if (i <= mx) update(x << 1, lx, mx, i, v);
else update(x << 1 | 1, mx + 1, rx, i, v);
t[x] = t[x << 1] + t[x << 1 | 1];
}
int query(int x, int lx, int rx, int l, int r) {
if (l > r) return 0;
if (l > rx || lx > r) return 0;
if (l <= lx && r >= rx) return t[x];
int mx = (lx + rx) >> 1;
return query(x << 1, lx, mx, l, r) + query(x << 1 | 1, mx + 1, rx, l, r);
}
long long count_swaps(vector<int> s) {
int n = s.size();
long long ans = 0;
vector<int> a[n][2];
vector<bool> taken(n);
for (int i = n - 1; i >= 0; i--) {
if (s[i] < 0) a[-s[i]][0].push_back(i);
else a[s[i]][1].push_back(i);
}
for (int i = 1; i <= n; i++) update(1, 1, n, i, 1);
for (int i = 0; i < n; i++) {
if (taken[i]) continue;
int si = abs(s[i]);
int other = (s[i] < 0 ? a[si][1].back() : a[si][0].back());
ans += query(1, 1, n, i + 2, other);
update(1, 1, n, other + 1, 0);
if (s[i] > 0) ans++;
taken[other] = true;
a[si][0].pop_back();
a[si][1].pop_back();
}
return ans;
}
