#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll merge_sort(vector<int> &a, int p, int k) {
if (p == k) {
return 0;
}
ll x = merge_sort(a, p, (p+k)/2)+merge_sort(a, (p+k)/2+1, k);
int r = (p+k)/2-p+1;
queue<int> s;
int in1 = p, in2 = (p+k)/2+1;
while (in1 <= (p+k)/2 && in2 <= k) {
if (in1 > (p+k)/2) {
s.push(a[in2]);
in2++;
x += r;
continue;
}
if (in2 > k) {
s.push(a[in1]);
in1++;
continue;
}
if (a[in1] < a[in2]) {
s.push(a[in1]);
in1++;
r--;
}
else {
x += r;
s.push(a[in2]);
in2++;
}
}
return x;
}
long long count_swaps(std::vector<int> s) {
int n = s.size();
map<int, queue<int>> mp;
for (int i = 0; i < n; i++) {
mp[s[i]].push(i);
}
vector<int> p (n, 0);
vector<bool> odw (n, 0);
int l = 0;
for (int i = 0; i < n; i++) {
if (odw[i]) continue;
int j = mp[-s[i]].front();
mp[-s[i]].pop();
mp[s[i]].pop();
odw[i] = 1;
odw[j] = 1;
if (s[i] < 0) {
p[i] = l;
p[j] = l+1;
}
else {
p[j] = l;
p[i] = l+1;
}
l +=2;
}
return merge_sort(p, 0, n-1);
}
