#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
long long merge(int a[], int beg, int mid, int end)
{
int i = beg, j = mid;
long long inv = 0;
while(i < mid and j < end)
if(a[i] < a[j]) i++;
else inv += mid - i, j++;
std::inplace_merge(a + beg, a + mid, a + end);
return inv;
}
// sort arr[beg:end) and return no. of inversions
long long inversions(int a[], int beg, int end)
{
long long inv = 0;
if(end - beg < 2) return 0;
if(end - beg == 2)
{
if(a[beg] < a[beg + 1]) return 0;
else return swap(a[beg], a[beg + 1]), 1;
}
int mid = (beg + end) >> 1;
inv += inversions(a, beg, mid);
inv += inversions(a, mid, end);
inv += merge(a, beg, mid, end);
return inv;
}
long long count_swaps(vector<int> a) {
int n = (int) a.size();
int p[n];
queue<int> idx[n / 2 + 1];
for(int i = 0, c = 0; i < n; i++)
{
if(a[i] < 0)
{
p[i] = c;
idx[-a[i]].push(c + 1);
c += 2;
}
}
for(int i = 0; i < n; i++) {
if(a[i] > 0)
{
p[i] = idx[a[i]].front();
idx[a[i]].pop();
}
}
return inversions(p, 0, n);
}
