#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
struct BIT {
vt<int> fen;
BIT(int n) {
fen.resize(n);
}
void upd(int i, int v) {
for (; i < size(fen); i += i+1 & -i-1)
fen[i] += v;
}
int qry(int i) {
int ret = 0;
for (; ~i; i -= i+1 & -i-1)
ret += fen[i];
return ret;
}
int qry(int l, int r) {
return qry(r) - qry(l-1);
}
};
ll count_swaps(vt<int> s) {
const int N = size(s) >> 1;
vt<int> A[N], B[N];
FOR(i, 0, 2*N-1)
(s[i] > 0 ? B[s[i]-1] : A[-s[i]-1]).push_back(i);
int L[N], R[N], ii = 0;
ll ans = 0;
FOR(i, 0, N-1)
FOR(j, 0, size(A[i])-1) {
L[ii] = A[i][j], R[ii] = B[i][j];
if (L[ii] > R[ii])
ans++, swap(L[ii], R[ii]);
ii++;
}
int ord[N];
iota(ord, ord+N, 0);
sort(ord, ord+N, [&](const int &a, const int &b) {
return L[a] < L[b];
});
BIT fen(2*N);
FOR(x, 0, N-1) {
int i = ord[x];
ans += R[i] - L[i] - 1 - (L[i] + 1 < R[i]) * fen.qry(L[i]+1, R[i]-1);
fen.upd(R[i], 1);
}
return ans;
}
