#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vii = vector<vi>;
struct FENWICK {
int N;
vi A;
FENWICK(int n): N(n) {
A.resize(N + 1, 0);
}
void add(int i, int x) {
for (; i <= N; i += (i) & (-i))
A[i] += x;
}
int get(int i) {
int ret = 0;
for (; i > 0; i -= (i) & (-i))
ret += A[i];
return ret;
}
};
ll count_swaps(vi s) {
ll ats = 0;
int N = (int)s.size();
vb done(N, false);
vi other(N, -1);
{
vector<vii> pos(3, vii(N));
vii ind(3, vi(N, 0));
for (int i = 0; i < N; ++i)
{
int k = (s[i] > 0 ? 1 : 0);
int d = 1 - k;
int m = abs(s[i]);
if (ind[d][m] < (int)pos[d][m].size()) {
int kit = pos[d][m][ind[d][m]];
other[i] = kit;
other[kit] = i;
ind[d][m]++;
} else {
pos[k][m].emplace_back(i);
}
}
// for (auto u : other) printf("%d ", u);
}
FENWICK fen(N + 1);
for (int i = 0; i < N; ++i)
{
if (done[i]) continue;
int ot = other[i];
assert(i < ot);
int cn = fen.get(ot) - fen.get(i);
ats += ot - i - cn - 1;
if (s[i] > s[other[i]]) ats++;
done[other[i]] = done[i] = true;
fen.add(other[i], 1);
}
return ats;
}
