#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> t;
void upd(int k, int x) {
k++;
for (; k <= N; k += k & -k) {
t[k] += x;
}
}
int get(int k) {
k++;
int res = 0;
for (; k >= 1; k -= k & -k) {
res += t[k];
}
return res;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
long long count_swaps(vector<int> a) {
int n = a.size();
N = n;
t.resize(n + 1);
vector<set<int>> pos(n + 1), neg(n + 1);
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
pos[a[i]].insert(i);
}
else {
neg[-a[i]].insert(i);
}
}
for (int i = 0; i < n; i++) {
upd(i, 1);
}
vector<bool> vis(n);
long long res = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int j = 0;
if (a[i] > 0) {
j = *neg[a[i]].upper_bound(i);
}
else {
j = *pos[-a[i]].upper_bound(i);;
}
if (!vis[i]) upd(i, -1);
if (!vis[j]) upd(j, -1);
vis[i] = vis[j] = true;
res += get(i, j) + (a[i] > 0);
}
return res;
}
