#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
ll cntAndMerge(vector<ll>& A, ll l, ll m, ll r) {
ll nLeft = m - l + 1, nRight = r - m;
vector<ll> L(nLeft), R(nRight);
for (ll i = 0; i < nLeft; i++) {
L[i] = A[i + l];
}
for (ll j = 0; j < nRight; j++) {
R[j] = A[m + 1 + j];
}
ll res = 0;
ll i = 0, j = 0, k = l;
while (i < nLeft && j < nRight) {
if (L[i] <= R[j]) {
A[k] = L[i];
k++; i++;
} else {
A[k] = R[j];
k++; j++;
res += nLeft - i;
}
}
while (i < nLeft) {
A[k] = L[i];
k++; i++;
}
while (j < nRight) {
A[k] = R[j];
k++; j++;
}
return res;
}
ll cntInversions(vector<ll>& arr, ll l, ll r) {
ll res = 0;
if (l < r) {
ll m = (r + l) / 2;
res += cntInversions(arr, l, m);
res += cntInversions(arr, m + 1, r);
res += cntAndMerge(arr, l, m, r);
}
return res;
}
ll inversionCount(vector<ll> &arr) {
ll N = arr.size();
return cntInversions(arr, 0, N - 1);
}
ll count_swaps(vector<int> shoes) {
ll N = shoes.size();
ll negPointer = 0;
vector<ll> currentShoesRelative;
currentShoesRelative.resize(N);
map<ll, priority_queue<ll, vector<ll>, greater<ll> > > mapOfPQs;
for (ll i = 0; i < N; i++) {
if (shoes[i] > 0) {
mapOfPQs[shoes[i]].push(i);
}
}
for (ll i = 0; i < N; i++) {
if (shoes[i] < 0) {
currentShoesRelative[i] = negPointer;
ll nextNearest = mapOfPQs[-shoes[i]].top();
mapOfPQs[-shoes[i]].pop();
currentShoesRelative[nextNearest] = negPointer + 1;
negPointer += 2;
}
}
// for (ll i = 0; i < N; i++) {
// cout << currentShoesRelative[i] << " ";
// }
// cout << endl;
return inversionCount(currentShoesRelative);
}
// int main() {
// cout << count_swaps({-3, 2, 1, -1, -2, 2, -2, 3}) << endl;
// }
