#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
vector<int> left_shoose[100005];
vector<int> right_shoose[100005];
bool cmp(pair<int, int> a, pair<int, int>b){
return (a.first + a.second + (a.first > a.second)) < (b.first + b.second + (b.first > b.second));
}
int fen[200005];
void up(int idx, int chg){
while (idx <= 200000){
fen[idx] += chg;
idx += idx & (-idx);
}
return;
}
int re(int idx){
int res = 0;
while (idx > 0){
res += fen[idx];
idx -= idx & (-idx);
}
return res;
}
long long count_swaps(vector<int> s){
int n = s.size() / 2;
for (int i = 0; i < 2 * n; i ++){
if (s[i] < 0) left_shoose[-s[i]].push_back(i + 1);
else right_shoose[s[i]].push_back(i + 1);
}
vector<pair<int, int>> sigma;
for (int i = 1; i <= n; i ++){
while (right_shoose[i].size()){
sigma.push_back({left_shoose[i].back(), right_shoose[i].back()});
right_shoose[i].pop_back();
left_shoose[i].pop_back();
}
}
sort(sigma.begin(), sigma.end(), cmp);
long long res = 0;
for (int i = 0; i <n; i ++){
int left_val = sigma[i].first + re(sigma[i].first);
int right_val = sigma[i].second + re(sigma[i].second);
up(1, 1);
up(sigma[i].first, -1);
up(1, 1);
up(sigma[i].second, -1);
res += left_val + right_val;
if (left_val > right_val) res ++;
res -= 2 * i + 1;
res -= 2 * i + 2;
}
return res;
}
