#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 2e5 + 1;
int seg[4 * mxN];
int n;
void update(int tar, int l = 1, int r = n, int idx = 1) {
if (l == r) {
seg[idx] ^= 1;
return;
}
int mid = (l + r) >> 1;
if (tar <= mid) update(tar, l, mid, (idx << 1));
else update(tar, mid + 1, r, (idx << 1) + 1);
seg[idx] = seg[(idx << 1)] + seg[(idx << 1) + 1];
return;
}
int query(int tarl, int tarr, int l = 1, int r = n, int idx = 1) {
if (tarl > tarr) return 0;
if (tarl <= l && r <= tarr) return seg[idx];
else if (tarr < l || r < tarl) return 0;
int mid = (l + r) >> 1;
return query(tarl, min(tarr, mid), l, mid, (idx << 1)) + query(max(tarl, mid + 1), tarr, mid + 1, r, (idx << 1) + 1);
}
long long count_swaps(vector<int> s) {
n = s.size();
queue<int> q[n + 1];
int cnt = 1;
int a[n + 1];
for (int i = 0; i < n; i++) {
if (!q[s[i] + n / 2].empty()) {
a[i] = q[s[i] + n / 2].front();
q[s[i] + n / 2].pop();
} else {
a[i] = (s[i] < 0 ? cnt : cnt + 1);
q[-s[i] + n / 2].push((s[i] < 0 ? cnt + 1 : cnt));
cnt += 2;
}
}
// for (int i = 0; i < n; i++) cerr << a[i] << ' ';
// cerr << endl;
ll int ans = 0;
for (int i = 0; i < n; i++) {
ans += query(a[i] + 1, n);
update(a[i]);
}
return ans;
}
