#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> arr) {
int n = (int)arr.size();
map<int,queue<int>>index;
int time = 1;
for (int i = 0;i<n;++i){
if (arr[i] < 0){
index[arr[i]].push(i);
}
}
vector<int>order(n);
for(int i = 0;i<n;++i){
if (arr[i] < 0){
order[i] = time++;
order[index[-arr[i]].front()] = time++;
index[-arr[i]].pop();
}
}
function<long long(int,int,int)>merge = [&](int left,int mid,int right){
int i = left,j = mid + 1;
long long ans = 0;
vector<int>temp(right - left + 1);
int cur = 0;
while(i<=mid && j<=right){
if (order[i] > order[j]){
ans+=mid - i + 1;
temp[cur++] = order[j++];
}
else{
temp[cur++] = order[i++];
}
}
while(i<=mid){
temp[cur++] = order[i++];
}
while(j<=right){
temp[cur++] = order[j++];
}
int p = 0;
while(left<=right){
order[left++] = temp[p++];
}
return ans;
};
function<long long(int,int)>merge_sort =[&](int left,int right){
if (left>=right)return 0LL;
int mid = (left + right)>>1;
long long ans = 0;
ans+=merge_sort(left,mid);
ans+=merge_sort(mid + 1,right);
ans+=merge(left,mid,right);
return ans;
};
return merge_sort(0,n - 1);
}
