#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll tree[271828];
void up(int x, ll k) {
x++;
while (x < 271828) {
tree[x] += k;
x += (x & (-x));
}
}
ll q(int x) {
x++;
ll ans = 0;
while (x > 0) {
ans += tree[x];
x -= (x & (-x));
}
return ans;
}
long long count_swaps(std::vector<int> s) {
memset(tree, 0, sizeof(tree));
int sz = s.size();
for (int i = 0; i < sz; i++) up(i, 1);
int n = sz/2;
priority_queue<int, vector<int>, greater<int>> l[sz];
priority_queue<int, vector<int>, greater<int>> r[sz];
for (int i = 0; i < sz; i++) {
int temp = s[i];
if (temp > 0) r[temp].push(i);
else l[-temp].push(i);
}
ll ans = 0;
for (int i = 0; i < sz; i++) {
if (q(i)-q(i-1) == 0) continue;
int temp = s[i];
int temp2;
if (temp > 0) {
temp2 = l[temp].top();
up(temp2, -1);
ans += q(temp2-1)-q(i-1);
}
else {
temp2 = r[-temp].top();
up(temp2, -1);
ans += q(temp2-1)-q(i);
}
l[abs(temp)].pop();
r[abs(temp)].pop();
up(i, -1);
}
return ans;
}
