#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];
// Range Update Point Query
template<typename T>
struct FenwickTree {
vector<T> bit;
const int N;
FenwickTree (int n) : N (n + 5) {
bit.clear();
bit.resize(N + 500);
}
void update (int idx, T delta) {
for (; idx < N; idx += idx & (- idx)) {
bit[idx] += delta;
}
}
void range_update (int hi, int lo, 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<long long> 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;
if (lower_bound (g[delta + OFF].begin(), g[delta + OFF].end(), i) == g[delta + OFF].end()) {
return -1;
}
int nxt = *lower_bound (g[delta + OFF].begin(), g[delta + OFF].end(), i);
is_valid[cur] = is_valid[nxt] = 0;
// cout << cur << ' ' << nxt << '\n';
if (cur > nxt) {
return -1;
}
int p1 = cur + fen.query (cur);
int p2 = nxt + fen.query (nxt);
if (p1 > p2) {
return -1;
}
res += p2 - p1 - (delta > 0);
fen.range_update (cur + 1, nxt - 1, + 1);
}
return 1;
}
