#include "shoes.h"
#include <set>
using namespace std;
int n;
vector<int> st;
void build(int id, int tl, int tr) {
if (tl == tr) {
st[id] = 1;
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
build(x, tl, tm);
build(y, tm + 1, tr);
st[id] = st[x] + st[y];
}
void update(int id, int tl, int tr, int i) {
if (tl == tr) {
st[id] = 0;
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
if (i <= tm)
update(x, tl, tm, i);
else
update(y, tm + 1, tr, i);
st[id] = st[x] + st[y];
}
int query(int id, int tl, int tr, int l, int r) {
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r) return st[id];
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
return query(x, tl, tm, l, r) + query(y, tm + 1, tr, l, r);
}
void update(int i) {
update(0, 0, n - 1, i);
}
int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
int abs(int x) {
return (x < 0 ? -x : x);
}
long long count_swaps(vector<int> a) {
n = a.size();
st.resize(4 * n);
build(0, 0, n - 1);
vector<set<int>> A(n + 1);
for (int i = 0; i < n; i++) {
A[abs(a[i])].insert(i);
}
long long res = 0;
for (int i = 0; i < n; i++) {
if (query(i, i) == 0) continue;
int x = abs(a[i]);
int id = *A[x].upper_bound(i);
A[x].erase(i);
A[x].erase(id);
update(i);
update(id);
res += query(i, id) + (a[i] > 0);
}
return res;
}
