#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAX = 1e6;
vector<int> fenwick(MAX + 10);
void update(int n) {
for (; n <= MAX; n += n & -n) fenwick[n]++;
}
int query(int n) {
int S = 0;
for (; n; n -= n & -n) S += fenwick[n];
return S;
}
int count_swaps(vector<signed> S) {
const int N = S.size();
vector<bool> done(N);
vector<int> A(N);
map<int, int> used;
map<int, vector<int> > memo;
for (int i = 0; i < N; i++) memo[S[i]].push_back(i);
int n = 0;
for (int i = 0; i < N; i++) {
if (done[i]) continue;
const int nxt = *lower_bound(memo[-S[i]].begin(), memo[-S[i]].end(), used[-S[i]]);
used[-S[i]] = nxt + 1;
used[S[i]] = i + 1;
if (S[i] > 0) A[i] = n + 1, A[nxt] = n;
else A[i] = n, A[nxt] = n + 1;
n += 2;
done[nxt] = 1;
}
int ans = 0;
for (int i = 0; i < N; i++) {
ans += query(N - A[i]);
update(N - A[i]);
}
return ans;
}
