#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define sum(x) accumulate(all(x), 0LL)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
struct FTree {
int n;
vi ft;
FTree(int _n) : n(_n + 9), ft(n, 0) {}
void add(int p) {
for (++p; p < n; p += p & -p) ft[p]++;
}
int get(int p) {
int s = 0;
for (; p > 0; p -= p & -p) s += ft[p];
return s;
}
};
ll count_swaps(vi s) {
const int n = sz(s);
vector<vi> where(2 * n + 1);
forn(i, n) where[s[i] + n].pb(i);
forn(i, 2 * n + 1) reverse(all(where[i]));
vi perm(n, -1);
int pos = 0;
auto clear = [&](vi &p) {
while (perm[p.back()] != -1) p.pop_back();
};
forn(i, n) if (perm[i] == -1) {
int a = i, x = s[i];
clear(where[-x + n]);
int b = where[-x + n].back();
if (x > 0) swap(a, b);
perm[a] = pos++;
perm[b] = pos++;
}
FTree ft(n);
ll ret = 0;
dforn(i, n) {
ret += ft.get(perm[i]);
ft.add(perm[i]);
}
return ret;
}
