#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int OFF = 1e5 + 5;
const int N = 2 * OFF;
bitset<N> is_valid;
vector<int> g [N];
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();
FenwickTree fen (N);
s.insert (s.begin(), 0);
for (int i = 1; i <= n; i++) {
g[s[i] + OFF].emplace_back(i);
}
is_valid.set();
for (int i = 1; i <= n; i++) {
if (is_valid.test(i) == 0) continue;
int delta = s[i] * -1;
int cur = i;
int nxt = *lower_bound (g[delta + OFF].begin(), g[delta + OFF].end(), i);
is_valid[cur] = is_valid[nxt] = 0;
assert (cur < nxt);
int p1 = cur + fen.query (cur);
int p2 = nxt + fen.query (nxt);
assert (p1 < p2);
res += p2 - p1 - (delta > 0);
fen.range_update (cur + 1, nxt - 1, + 1);
}
return res;
}
