#include <bits/stdc++.h>
#include "shoes.h"
// #include "grader.cpp"
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define nl '\n'
struct Fenw {
int n;
vector<int> t;
Fenw(int n) : n(n), t(n + 1) {}
void update(int i, int x) {
i++;
for(; i <= n; i += i & -i) t[i] += x;
}
int get(int i) {
int res = 0;
for(; i >= 1; i -= i & -i) res += t[i];
return res;
}
int get(int l, int r) {
return get(r + 1) - get(l);
}
};
long long count_swaps(vector<int> s) {
int n = s.size();
long long ans = 0;
Fenw fn(n);
bool flag = 0;
array <set<int>, 2> st;
for(int i = 0; i < n; i++) {
st[s[i] > 0].emplace(i);
}
for(int i = 0; i < n; i++) {
if(fn.get(i, i)) continue;
int x = s[i] > 0;
if(flag != x) {
int y = !x;
int j = *st[y].begin();
st[y].erase(st[y].begin());
ans += j - i - fn.get(i, j);
fn.update(j, 1);
}
st[x].erase(i);
// for(int j = 0; j < n; j++) {
// cout << fn.get(j, j) << ' ';
// }
// cout << nl;
flag = !flag;
}
return ans;
}
/**
4
2 -2 2 2 -2 -2 -2 2
**/
