#include "shoes.h"
#include <bits/stdc++.h>
#define flag(_a) cout << "Still alive at flag " << _a << '\n';
#define dbg(_a, _b) cout << "var " << _a << " -> " << _b << '\n';
#define dbg_itv(_l, _r, _val) cout << "itv (" << _l << ", " << _r << ") -> " << _val << '\n';
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 2;
ll n;
ll bit[maxn];
vector<queue<int> > L, R;
ll lb(ll x) {return x & (-x);}
void build() {
for (ll i = 1; i <= n; i++) {
bit[i] = (i - (i-lb(i)+1) + 1);
}
}
void modify(ll x) {
for (; x <= n; x += lb(x)) {
bit[x]--;
}
}
ll qry(ll x) {
ll sum = 0;
for (; x > 0; x -= lb(x)) {
sum += bit[x];
}
return sum;
}
ll count_swaps(vector<int> s) {
n = (int)s.size();
L.resize(n/2+1);
R.resize(n/2+1);
for (int i = 0; i < n; i++) {
if (s[i] < 0) L[-s[i]].push(i+1);
else R[s[i]].push(i+1);
}
build();
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (qry(i)) {
if (s[i] < 0) {
int lpos = i, rpos = R[-s[i]].front();
L[-s[i]].pop(), R[-s[i]].pop();
ans += qry(rpos - 1) - qry(lpos);
modify(lpos), modify(rpos);
} else {
int lpos = L[s[i]].front(), rpos = i;
L[s[i]].pop(), R[s[i]].pop();
ans += qry(lpos - 1) - qry(rpos - 1);
modify(lpos), modify(rpos);
}
}
}
return ans;
}
/*
2
2 1 -1 -2
*/
