#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
ll n;
vector<ll> toSort;
void conquer(int l_l, int l_r, int r_l, int r_r, ll &invCount) {
ll szL = l_r - l_l + 1;
ll szR = r_r - r_l + 1;
queue<ll> a, b;
queue<ll> res;
for(int i = l_l; i <= l_r; i++) a.push(toSort[i]);
for(int i = r_l; i <= r_r; i++) b.push(toSort[i]);
while(szL && szR) {
if(a.front() < b.front()) {
res.push(a.front());
a.pop();
szL--;
} else {
res.push(b.front());
b.pop();
invCount += szL;
szR--;
}
}
while(szL) {
res.push(a.front());
a.pop();
szL--;
}
while(szR) {
res.push(b.front());
b.pop();
szR--;
}
for(int i = l_l; i <= r_r; i++) {
toSort[i] = res.front();
res.pop();
}
}
void divide(int l, int r, ll &invCount) {
if(l != r) {
int m = l + (r-l)/2;
divide(l, m, invCount);
divide(m+1, r, invCount);
conquer(l, m, m+1, r, invCount);
}
}
ll count_swaps(vector<int> a) {
n = size(a);
/*
we probably can find a solution that doesnt swap two left shoes
l...r...L...R (no swap between l and L)
l...r...R...l (no swap between l and L)
l...L...R...r (swap r across LR)
l...L...r...R (swap r across L)
l...R...r...L (swap r across R, swap R across L?)
l...R...L...r
a b c
goes to either lrLR or LRlr
lrLR cost: a+b+c+b
LRlr cost: b+a+b+c
is it actually LMFAO
lets see
*/
vector<queue<ll>> spot(n+n+5);
toSort = vector<ll>(n, -1);
int x = 0;
for(int i = 0; i < n; i++) {
int pos = abs(a[i]);
int neg = n + pos;
if(a[i] < 0) {
if(spot[pos].empty()) {
spot[neg].push(i);
} else {
toSort[i] = x++;
toSort[spot[pos].front()] = x++;
spot[pos].pop();
}
} else {
if(spot[neg].empty()) {
spot[pos].push(i);
} else {
toSort[spot[neg].front()] = x++;
toSort[i] = x++;
spot[neg].pop();
}
}
}
ll invCount = 0;
divide(0, n-1, invCount);
return invCount;
}
