#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2e5 + 5;
int n, m;
queue<int> pos[maxn][2];
pii a[maxn];
vector<pair<ll, pair<int,int>>> cost;
int fen[maxn];
int calc(pair<int,int> x, pair<int,int> y) {
return (x.first > y.first) + (x.first > y.second) + (x.second > y.first) + (x.second > y.second);
}
void update(int x, int val) {
x++;
while(x > 0) {
fen[x] += val;
x -= x&-x;
}
}
int sum(int x) {
x++;
int sum = 0;
while(x <= n) {
sum += fen[x];
x += x&-x;
}
return sum;
}
long long count_swaps(std::vector<int> s) {
n = s.size(); m = 0;
for(int i = 0; i < n; i++) {
int x = abs(s[i]);
pos[x][s[i] < 0].push(i);
// printf("%d: %d\n",x,s[i]<0);
if(!pos[x][0].empty() && !pos[x][1].empty()) {
a[++m] = {pos[x][1].front(), pos[x][0].front()};
// printf("{%d, %d}\n",a[m].first,a[m].second);
pos[x][0].pop(); pos[x][1].pop();
}
}
for(int i=1;i<=m;i++) {
int x = a[i].first, y = a[i].second;
cost.push_back({x + y - (x < y), {x, y}});
}
sort(cost.begin(), cost.end());
ll ans = 0;
for(int i=0;i<m;i++) {
int x = cost[i].second.first, y = cost[i].second.second;
// printf("%lld %d %d: %lld\n",cost[i].first,cost[i].second.first,cost[i].second.second,cost[i].first - 4 * i);
ans += cost[i].first + sum(x) + sum(y) - 4 * i;
update(x, 1); update(y, 1);
}
return ans;
}
