#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct SGT {
int n;
vector<ll> t, lazy;
SGT(int _n) : n(_n) {
t.resize(4 * n, 0), lazy.resize(4 * n, 0);
}
void push(int v) {
t[2 * v] += lazy[v];
lazy[2 * v] += lazy[v];
t[2 * v + 1] += lazy[v];
lazy[2 * v + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int l, int r, int L, int R) {
if (R < l or r < L) return;
else if (L <= l and r <= R) t[v] += 1, lazy[v] += 1;
else {
push(v);
int mid = (l + r) / 2;
update(2 * v, l, mid, L, R);
update(2 * v + 1, mid + 1, r, L, R);
t[v] = t[2 * v] + t[2 * v + 1];
}
}
ll query(int v, int l, int r, int i) {
if (l == r) return t[v];
else {
push(v);
int mid = (l + r) / 2;
if (i <= mid) return query(2 * v, l, mid, i);
else return query(2 * v + 1, mid + 1, r, i);
}
}
void update(int L, int R) {
update(1, 0, n - 1, L, R);
}
ll query(int x) {
return query(1, 0, n - 1, x);
}
};
ll n;
vector<queue<ll>> l, r;
ll count_swaps(vector<int> s) {
n = s.size();
l.resize((n / 2) + 1), r.resize((n / 2) + 1);
SGT sgt = SGT(n);
ll cnt = 0;
for (int i = 0; i < n; i++) {
int x = abs(s[i]);
if (s[i] < 0) {
if (not r[x].empty()) {
cnt += i - (r[x].front() + sgt.query(r[x].front()));
sgt.update(r[x].front(), i);
r[x].pop();
} else l[x].push(i);
} else {
if (not l[x].empty()) {
cnt += i - (l[x].front() + sgt.query(l[x].front())) - 1;
sgt.update(l[x].front(), i);
l[x].pop();
} else r[x].push(i);
}
}
return cnt;
}
