#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(n);
forn(i, n) if (s[i] > 0) where[s[i] - 1].pb(i);
forn(i, n) reverse(all(where[i]));
vi perm(n);
int pos = 0;
forn(i, n) if (s[i] < 0) {
perm[i] = pos++;
int j = where[-s[i] - 1].back();
where[-s[i] - 1].pop_back();
perm[j] = pos++;
}
FTree ft(n);
ll ret = 0;
dforn(i, n) {
ret += ft.get(perm[i]);
ft.add(perm[i]);
}
return ret;
}
