#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int N = 2e5 + 5;
bitset<2 * N> is_valid;
struct FenwickTree {
vector<int> bit;
const int N;
FenwickTree (int n) : N (n + 5) {
bit.clear (); bit.resize (N);
}
void update (int idx, int delta) {
for (; idx < N; idx += idx & (- idx)) {
bit[idx] += delta;
}
}
void range_update (int lo, int hi, int delta) {
update (lo, + delta);
update (hi + 1, - delta);
}
int query (int idx) {
int res = 0;
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();
const int OFF = N + 5;
vector<int> g [N + 5000];
for (int i = 0; i < n; i++) {
g[s[i] + OFF].emplace_back(i);
}
FenwickTree fen (N + 5000);
for (int i = 0; i < n; i++) {
if (is_valid[i] == true) continue;
int target = s[i] * -1;
int primeiro = i + fen.query (i + 1);
int p = *lower_bound(g[target + OFF].begin(), g[target + OFF].end(), i);
int segundo = p + fen.query (p + 1);
is_valid[p] = true;
// assert (primeiro < segundo);
res += segundo - primeiro;
if (s[i] < 0) --res;
fen.range_update (p + 1, N, - 1);
}
return res;
}
