#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
const int N = 1e5 + 3;
queue<int> pz[N][2];
struct fenwick_tree {
vector<int> bit;
void init(int n) {
bit.assign(n + 1, 0);
}
int sum(int i) {
int s = 0;
while (i > 0) {
s += bit[i];
i -= (i & (-i));
}
return s;
}
void add(int i, int val, int n) {
while (i > 0 && i <= n) {
bit[i] += val;
i += (i & (-i));
}
}
int get(int l, int r) {
return sum(r) - (l > 0 ? sum(l-1) : 0);
}
}; fenwick_tree fenwick;
long long count_swaps(vector<int> s) {
int n = s.size();
fenwick.init(n);
set<pair<int, int>> st;
for (int i = 0; i < n; i++) {
int tp = (s[i] < 0 ? 0 : 1);
pz[abs(s[i])][tp].push(i);
st.insert({i, s[i]});
}
ll ans = 0;
for (int i = 0; i < n; i += 2) {
auto [j, sj] = *st.begin();
st.erase(st.begin());
int tp = (sj < 0 ? 0 : 1);
pz[abs(sj)][tp].pop();
int k = pz[abs(sj)][tp^1].front();
pz[abs(sj)][tp^1].pop();
st.erase(st.find(make_pair(k, -sj)));
int add = fenwick.get(k, n);
fenwick.add(k, 1, n);
int raz = (k+add-i) - (tp == 0);
ans += raz;
}
return ans;
}
