#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int OFF = 1e5 + 5;
const int N = 2 * OFF;
bitset<N> is_used;
vector< set<int> > g (N);
template<typename T>
struct FenwickTree {
vector<T> bit;
const int N;
FenwickTree (int n) : N (n + 5) {
bit.clear();
bit.resize(N);
}
void update (int idx, T delta) {
for (; idx < N; idx += idx & (- idx)) {
bit[idx] += delta;
}
}
void range_update (int lo, int hi, T delta) {
update (lo, + delta);
update (hi + 1, - delta);
}
T query (int idx) {
T res {};
for (; idx > 0; idx -= idx & (- idx)) {
res += bit[idx];
}
return res;
}
};
long long count_swaps(vector<int> s) {
long long res = 0;
const int n = (int) s.size();
FenwickTree<int> fen (N);
s.insert (s.begin(), 0);
is_used.reset();
for (int i = 1; i <= n; i++) {
g[s[i] + OFF].insert(i);
}
for (int i = 1; i <= n; i++) {
if (is_used.test(i)) continue;
int delta = s[i] * -1;
int cur = i;
int nxt = *g[delta + OFF].begin();
is_used.set(cur);
is_used.set(nxt);
int p1 = cur + fen.query (cur);
int p2 = nxt + fen.query (nxt);
res += p2 - p1 - (s[i] < 0);
g[s[i] + OFF].erase(i);
g[delta + OFF].erase(nxt);
fen.range_update (cur + 1, nxt - 1, + 1);
}
return res;
}
