#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int power2(int n) {
if (n == 0) return 1;
else return 2*power2(n - 1);
}
int h;
vector<LL> tree;
void modify(int pos, LL inc) {
pos += power2(h);
tree[pos] += inc;
while (pos != 1) {
if (pos % 2) pos--;
tree[pos/2] = tree[pos] + tree[pos + 1];
pos /= 2;
}
//for (auto elem: tree) cout << elem << " ";
// cout << '\n';
}
LL query(int right) {
int left = power2(h);
right += power2(h);
LL ret = 0;
while (right != left) {
if (right % 2 == 0) {
ret += tree[right];
right--;
}
right /= 2;
left /= 2;
}
ret += tree[left];
return ret;
}
LL count_swaps(vector<int> shoes) {
int n = shoes.size();
h = 1;
while (power2(h) <= n + 1) h++;
tree.assign(power2(h + 1), 0);
for (int i = 0; i < n; i++) modify(i, 1);
map<int, queue<int>> mp;
for (int i = 0; i < n; i++) {
mp[shoes[i]].push(i);
}
vector<bool> used(n, false);
LL ans = 0;
for (int i = 0; i < n; i++) {
if (!used[i]) {
used[i] = true;
mp[shoes[i]].pop();
queue<int>& cur = mp[0 - shoes[i]];
ans += query(cur.front())-query(i)-1;
//cout << query(cur.front()) << " " << query(i) <<" " << i << '\n';
if (shoes[i] > 0) ans++;
modify(cur.front(), -1);
modify(i, +1);
used[cur.front()] = true;
cur.pop();
}
}
return ans;
}
